H3X's blog

Lexicographically smallest min cut.
By H3X, 12 years ago, In English

Can anyone share a method or an idea to find lexicographically smallest minimum cut in a graph.

http://en.wikipedia.org/wiki/Minimum_cut

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

»
12 years ago, # |
  Vote: I like it +23 Vote: I do not like it

this is sounds very similar like one of the facebook hacker cup task this year..

So my first try would be, find the smallest minimum cut, let denote this number C..

After that make some greedy algo: find the smallest node id which can be a part of some cut which volumen is C.

So go through node and erase node v, after that run find minimum cut algo, if this cut volumen is C-1 we found the first node of the lexicographically smallest minimum cut..

after that find the second node, and so on.. minimum cut algo is O(N^3) , it seems to enough go through the node just once (this is N step), and we erase every edge maximum twice so this algo is about O(N^4*M)

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, that seems to work thanks, but isn't it's complexity O(N^3*(N+2*M))?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Sorry I wasn't calculate it precisely.. Now it seems to me, this is O(N^4+2*M).

    → Reply