radoslav11's blog

Counter sample for Kuhn's maximum matching algorithm.
By radoslav11, history, 7 years ago, In English

Hello!

My question is simple. Can someone give me a test sample for maximum matching in bipartite graphs on which Kuhn's algorithm preforms badly (something like O(N * M) in time). Thanks in advance.

  • Vote: I like it
  • +30
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it -18 Vote: I do not like it

In a complete bipartite graph, Kuhn's would traverse the longest augmenting path first: http://imgur.com/a/dXXRq

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +74 Vote: I do not like it

    It seems to be 1 + 2 + ... + N = O(N2) in that case

    → Reply
»
7 years ago, # |
  Vote: I like it +28 Vote: I do not like it

It will take longest time if it fails to augment the matching. Then it will have to look through all edges in adjacency lists of reachable nodes. So we take a full bipartite graph with n/4 + n/4 nodes and another n/2 nodes connect to any node in the right half, m=n^2/16+n/2. Ignoring the part where we find matching in full part the total number of times we will look at some edge is n/2 (m-n/2+1) = O(nm)

→ Reply