A Fast Matching Algorithm Algorithm 54 Bimatch-Hopcroft-Karp G 1: M 2: repeat 3: let P fP1;:::;Pkg be maximal set of 4: vertex-disjoint, shortest augmenting path w.r.t. M. 5: M M P1[ [Pk 6: until P 7: return M We call one iteration of the repeat-loop a phase of the algorithm. EADS 22 The Hopcroft-Karp Algorithm c Ernst Mayr, Harald Räcke 568/596 Analysis Lemma 98 Given a matchingM and a maximal matchingM there exist jM j jMjvertex-disjoint augmenting path w.r.t. M.
Proof: æ Similar to the proof that a matching is optimal iff it does not contain an augmenting paths. æ Consider the graph G V;M M , and mark edges in this graph blue if they are in M and red if they are in M . æ The connected components of G are cycles and paths. æ The graph contains k jM j jMj more red edges than blue edges. æ Hence, there are at least k components that form a path starting and ending with a blue edge. These are augmenting paths w.r.t. M. EADS 22 The Hopcroft-Karp Algorithm c Ernst Mayr, Harald Räcke 569/596 Analysis Lemma 98 Given a matchingM and a maximal matchingM there exist jM j jMjvertex-disjoint augmenting path w.r.t. M. Proof: æ Similar to the proof that a matching is optimal iff it does not contain an augmenting paths. æ Consider the graph G V;M M , and mark edges in this graph blue if they are in M and red if they are in M . æ The connected components of G are cycles and paths. æ The graph contains k jM j jMj more red edges than blue edges. æ Hence, there...
Website: wwwmayr.informatik.tu-muenchen.de | Filesize: -
No of Page(s): 25
Download A Fast Matching Algorithm.pdf
No comments:
Post a Comment