The Hopcroft-Karp Algorithm c Ernst Mayr, Harald Räcke 568 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 Analysis æ Let P1;:::;Pk be a maximal collection of vertex-disjoint, shortest augmenting paths w.r.t. M (let ‘ jPij). æ M0 M P1[ [Pk M P1 Pk. æ Let P be an augmenting path in M0. Lemma 99 The setA M M0 P P1[ [Pk P contains at least k 1 ‘edges. EADS 22 The Hopcroft-Karp Algorithm c Ernst Mayr, Harald Räcke 570 Analysis Proof. æ The set describes exactly the symmetric difference between matchings M and M0 P. æ Hence, the set contains at least k 1 vertex-disjoint augmenting paths w.r.t. M as...
Website: wwwmayr.informatik.tu-muenchen.de | Filesize: -
No of Page(s): 8
Download A Fast Matching Algorithm.pdf
No comments:
Post a Comment