013's blog

Dinic's Algorithm For Unit Capacity Graph
By 013, history, 8 years ago, In English

Here it is written that Dinic's algorithm can run in O(min{V3 / 2, E1 / 2}E) time for graphs with unit capacity edges. Do I need to modify dinic's code in order to achieve that time bound? If yes can anyone give me an example code.

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

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

You don't need to do anything, just make sure that the edges are with unit (or equal) capacities.

→ Reply