Dynamic Tree Data Structure For Improved Dinic's Algorithm

Question

I want to apply Dinic's algorithm with dynamic tree. But I find very few sources. especially about the dynamic tree. It would be great if there is a good source with detailed explains or some simple sources code which uses dynamic tree.

Any one come across something like that? Thanks in advance

Answer 1

The basic idea for improvement is avoiding premature pessimization in Dinic's algorithm. As opposed to preflow/push algorithms, Dinic's algorithm searches for paths in the residual flow graph. Once such a flow is addressed, instead of starting a new search, the modified algorithm deals with paths found in the previous search.

You can find here a very readable introduction for this, including an implementation of the data structure itself. here is a more detailed lecture. Finally, A Data Structure for Dynamic Trees (by Sleator and Tarjan) is the original paper focussing on the implementation of the data structure itself.