Praktyczna implementacja algorytmu Micali-Vazirani

Algorytm Micali-Vazirani, znajdujący skojarzenia maksymalne w dowolnych grafach, był pierwszym algorytmem, którego złożoność równała się tej osiąganej przez klasyczne algorytmy dla grafów dwudzielnych. Późniejsze publikacje uzupełniły początkowo nieprecyzyjne opis i dowód algorytmu. Niniejsza praca omawia zasady jego działania i szczegóły implementacji.The Micali-Vazirani matching algorithm for general graphs was the first algorithm to achieve the time complexity of classic solutions to the same problem for bipartite graphs. Despite the initial lack of precision in its description and proof, newer publications have clarified and simplified its structure. We present an overview and an implementation of the algorithm