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

Malathion

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.

Rhotacism

Actually I have read first two sources quickly before, and did not understand much. But I do understand Dinic's algorithm. Maybe my problem is dynamic tree which I don't know at all. Seems like these are the best resources available, let me go over them again slowly. Thanks! :) – Malathion

@alim Then check the third. I think it is the one you want. – Rhotacism

It's good to give links descriptive titles (the third one is A Data Structure for Dynamic Trees, DANIEL D. SLEATOR AND ROBERT ENDRE TARJAN), so that, when links inevitably rot, Google can help find those things again. In the meantime, I have added those links to the wayback machine. (web.archive.org/web*/arl.wustl.edu/~jst/cse/542/text/sec19.pdf, for example) – Arin

@Arin Thanks! Modified to a more descriptive link. You're right. – Rhotacism