DocumentCode :
2175354
Title :
An O(v|v| c |E|) algoithm for finding maximum matching in general graphs
Author :
Micali, Silvio ; Vazirani, Vijay V.
fYear :
1980
fDate :
13-15 Oct. 1980
Firstpage :
17
Lastpage :
27
Abstract :
In this paper we present an 0(√|V|¿|E|) algorithm for finding a maximum matching in general graphs. This algorithm works in ´phases´. In each phase a maximal set of disjoint minimum length augmenting paths is found, and the existing matching is increased along these paths. Our contribution consists in devising a special way of handling blossoms, which enables an O(|E|) implementation of a phase. In each phase, the algorithm grows Breadth First Search trees at all unmatched vertices. When it detects the presence of a blossom, it does not ´shrink´ the blossom immediately. Instead, it delays the shrinking in such a way that the first augmenting path found is of minimum length. Furthermore, it achieves the effect of shrinking a blossom by a special labeling procedure which enables it to find an augmenting path through a blossom quickly.
Keywords :
Delay; History; Labeling; Scholarships;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1980., 21st Annual Symposium on
Conference_Location :
Syracuse, NY, USA
ISSN :
0272-5428
Type :
conf
DOI :
10.1109/SFCS.1980.12
Filename :
4567800
Link To Document :
بازگشت