Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In trying to implement the Hopcroft-Karp algorithm I have run into something I do not quite understand. In the step where you find the maximal set of vertex disjoint augmenting paths. How does one guarantee that you have the maximal set? Wikipedia suggests using a DFS from the unmatched verticies in one set, in the following case the lettered verticies, to the verticies that end the shortest augmenting paths in the other set, in this case 1 and 4. However, consider the following graph, which I hideously hacked together in Dia.

Hopcroft example graph

The edges that go from lettered nodes to numbered nodes are unmatched edges while the bold edges that go from numbered nodes to lettered nodes are currently matched edges. So now from what I understand of Wikipedia and some others (PDF) It is entirely possible in this step in the algorithm to take the path of (C,2,A,1) as the only augmenting path if you start with C and choose poorly. When obviously the right maximal set of disjoint shortest augmenting paths are (B,2,A,1) and (C,3,D,4). So How do you guarantee a maximal set of augmenting paths? Kudos also if you have a better idea for drawing graphs than Dia.

share|improve this question
1  
Wow. It only needs to be a maximal set, rather than a maximum set. Totally missed that. So my question is moot. –  janders Nov 20 '11 at 19:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.