Dinic's algorithm for max flow using dynamic trees

Revision en1, by Warriors_Cats, 2020-08-22 18:26:17

Hello, everyone! Can someone explain me how to merely implement Dinic's algorithm for maximum flow using the linear logarithmic behaviour provided by dynamic trees such as link/cut trees described by Tarjan and Sleator. Despite the fact that I have seeked for the so called O(VElogV) version of Dinic's algorithm, however I didn't manage to find any appropriate implementation for it. Here are some suggestive articles I have recently found: https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.cc.gatech.edu/~rpeng/18434_S15/blockingFlows.pdf&ved=2ahUKEwiDi676jK_rAhUPxosKHX3YAyMQFjABegQIARAB&usg=AOvVaw3AI1kk_L7dXi9oF8yheGsd and https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.arl.wustl.edu/~jst/cse/542/text/sec19.pdf&ved=2ahUKEwiFobDfia_rAhVN_CoKHYIrC-YQFjAAegQIAhAB&usg=AOvVaw30d3vyyxayE8XX1bZsEFZq. Thanks a lot in advance for any suggestion or link!

Tags dinic, maxflow, dynamic trees, link-cut trees

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Warriors_Cats 2020-08-22 18:26:17 935 Initial revision (published)