vivace_jr's blog

Dinics Algorith and Max Flows
By vivace_jr, history, 6 years ago, In English

There are so many different ways one can implement Dinic's, i have come across

1-> **EV^2** - https://github.com/PetarV-/Algorithms/blob/master/Graph%20Algorithms/Dinic%27s%20Algorithm.cpp
2-> **EV*log(maximum edge capcity)** -https://github.com/ADJA/algos/blob/master/Graphs/Dinic.cpp
3-> **EV*log(V)** - http://www.cs.tau.ac.il/~haimk/adv-alg-2013/dinic2013.pdf


Can anyone tell about or suggest some good tutorials where i can learn any of the following ->
1-> proof of Dinics
2-> proof of its timecomplexity (1st and 2nd types)
3-> implementation of third type(EVlog(V))
4-> proof of 2nd type
  • Vote: I like it
  • +43
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vivace_jr (previous revision, new revision, compare).

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

The following are suggested recent related publications that may be helpful in getting more information. Both references mention Dinic's algorithm.

  1. Solving the Maximum Flow Problem by a Modified Adaptive Amoeba Algorithm

  2. Whale Optimization Algorithm for Solving the Maximum Flow Problem

→ Reply