How to find an augmenting path?

Analysis If the shortest augmenting path w.r.t. a matchingM has‘ edges then the cardinality of the maximum matching is of size at most jM jjVj‘ 1. Proof. The symmetric difference betweenM andM containsjM j jMj vertex-disjoint augmenting paths. Each of these paths contains at least‘ 1 vertices. Hence, there can be at most jVj‘ 1 of them. EADS 22 The Hopcroft-Karp Algorithm c Ernst Mayr, Harald Räcke 573 Analysis Lemma 101 The Hopcroft-Karp algorithm requires at most 2pjVjphases. Proof. æ

After iterationb pjVjcthe length of a shortest augmenting path must be at leastbpjVjc 1 pjVj. æ Hence, there can be at mostjVj= pjVj 1 pjVj additional augmentations. EADS 22 The Hopcroft-Karp Algorithm c Ernst Mayr, Harald Räcke 574 Analysis Lemma 102 One phase of the Hopcroft-Karp algorithm can be implemented in timeO m . EADS 22 The Hopcroft-Karp Algorithm c Ernst Mayr, Harald Räcke 575 How to find an augmenting path? Construct an alternating tree. u x y w even nodes odd nodes Case 4: y is already contained in T as an even vertex can’t ignorey The cyclew$y x$w is called a blossom. w is called the base of the blossom (even node!!!). The pathu-w path is called the stem of the blossom. EADS 23 Maximum Matching in General Graphs c Ernst Mayr, Harald Räcke 576 Flowers and Blossoms Definition 103 A flower in a graphG V;E w.r.t. a matchingM and a (free) root noder, is a subgraph with two components: æ A stem is an even length alternating path that starts at the root noder and terminates at some nodew. We permit the possibility thatr w (empty stem). æ A blossom is an odd length alternating cycle that starts and terminates at the terminal nodew of a stem and has no other node in common with the stem. w is called the base of the blossom. EADS 23 Maximum Matching in General Graphs c Ernst Mayr, Harald Räcke 577 Flowers and Blossoms 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 11 EADS 23 Maximum Matching in General Graphs c Ernst Mayr, Harald Räcke 578 Flowers and Blossoms Properties: 1. A stem spans 2‘ 1 nodes and contains‘ matched edges for some integer‘ 0. 2. A blossom spans 2k 1 nodes and containsk matched edges for some integerk 1. The matched edges match all nodes of the blossom except the base. 3. The base of a blossom is an even node (if the stem is part of an alternating tree starting at r). EADS 23 Maximum Matching in General Graphs c Ernst Mayr, Harald Räcke 579 Flowers and Blossoms Properties: 4. Every nodex in the blossom (except its base) is reachable from the root (or from the base of the blossom) through two distinct alternating paths; one with even and one with odd length. 5. The even alternating...

Website: wwwmayr.informatik.tu-muenchen.de | Filesize: -
No of Page(s): 6
Download Analysis Analysis Analysis How to find an augmenting path?.pdf