Talk:Hopcroft–Karp algorithm

From Wikipedia, the free encyclopedia

This needs an explanation of the "run really fast" step (http://www.fysh.org/~katie/computing/methodologies.txt)

Contents

[edit] Shortestest

Is shortestest a word? ;D Ossian Hanning (talk) 20:37, 7 March 2008 (UTC)

[edit] Maximum vs. maximal

Changed the incorrect "maximum" to "maximal". —Preceding unsigned comment added by 80.145.225.62 (talk • contribs) 22:44, 3 October 2006 UTC

I agree. Thanks for persisting after the incorrect revert. —David Eppstein 05:55, 4 October 2006 (UTC)
I am sorry for the incorrect revert. I now think that I was wrong. I started this article because the algorithm was mentioned in the text of another article. The only reference I had was CLRS, where it said maximum. So when I saw this edit from an unregistered user, I checked in CLRS, saw that it said maximum, and assumed that the editor was either in error or mischevious. Sorry about this. Let me check that we agree with terminology:
If we go through a one-dimmensional state-space (x-axis below), where each state has a value (y-axis below),
           B                                                                   
           /\                                                                  
   A      /  \                                                                 
   /\    /    \                                                                
  /  \  /      \                                                               
 /    \/        \                                                              
/                \
then here both A and B are maximal points, while only B is a maximum. This is the terminology used in the article Matching.
The description in CLRS is actually just given as an exercise. I tried to solve it, but could not see how to find "maximum set of vertex-disjoint shortest augmenting paths" in O(V + E), so I just wrote the pseudocode for the algorithm as described, and put it in my ever-growing TODO to figure out the missing part. I now found a description of the pseudo-code which still says maximum in the comments, but the code clearly gives only something maximal. So the problem was simpler than I thought :) Thanks for the correction, and sorry about my error. Klem fra Nils Grimsmo 09:16, 4 October 2006 (UTC)

[edit] Difference from Dinic algorithm (Dinits' algorithm)?

What's the difference between this algorithm and Dinic algorithm? To me, it just looks like Dinic algorithm - only run on a specific input, so it has better time complexity than general-case Dinic. --Lukas Mach 22:27, 27 December 2006 (UTC)

It's none... H-K is 1973 algorithm and Dinic is 1976 algorithm. --Lukas Mach 01:55, 26 February 2007 (UTC)

[edit] Another estimations

Another estimations are O((V+E)V 1/2) and O(V 5/2): Lipski W., Kombinatoryka dla Programistow, [Combinatorics for Programmers], Wydawnictwa Naukowo-Techniczne, Warzawa, 1982.--Tim32 (talk) 10:58, 19 November 2007 (UTC)

[edit] Pseudocode

Is it just me, or is the pseudocode rather hard to read? For example, the first loop tripped me a bit, because it is some akward mixture of high-level functions ((u,v) in E) and low-level implementation (for node u, node v). Furthermore, the code checks for nodes being in M. I do not understand this, as M is a matching, and thus, a set of edges? --Tetha (talk) 05:49, 11 June 2008 (UTC)

M is a matching. When the code asks whether a vertex is in M, it means, is it an endpoint of one of the edges in M? I don't think it's any shorter or clearer than what's here, but if it would help you to see actual code for this algorithm, I have some here. (You can ignore the "imperfections" routine in that file; it solves a different and somewhat more complicated problem.) —David Eppstein (talk) 06:32, 11 June 2008 (UTC)
At least for me, the python code helps a lot. My definition of a matching came from graph theory, where a matching was just a set of edges that encode the matching (that is, an edge (u,v) in M means: u is matched with v). Your matching is a mapping that maps a node u to the node v, with u being matched with v. In your world, it makes a lot of sense to ask: node in matching, in mine, it did not (I rather would ask: exist an x with (x, u) in M.). Thank you. --Tetha (talk) 09:39, 11 June 2008 (UTC)