20
$\begingroup$

Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as link-cut trees).

  • Push relabel runs in $O(V^2E)$ or $O(V^3)$ or $O(V^2\sqrt{E})$ normally, but with dynamic trees $O(VE \log(V^2/E))$
  • Dinic's algorithm runs in $O(V^2E)$, but with dynamic trees $O(VE\log(V))$

However, practical implementations of max-flow algorithms in most libraries don't seem to make use of this data structure. Are dynamic trees ever used in practice for max flow computation? Or do they carry too much overhead to be useful for real world problem sizes?

Are there any other problem domains where link cut trees are used?

This question is related to a question that I asked on cstheory: Are any of the state of the art Maximum Flow algorithms practical?

Improve this question
$\endgroup$
2
  • $\begingroup$ overview/desc of link cut trees but only states "is useful for applications such as Network Flow" $\endgroup$
    – vzn
    Feb 5, 2013 at 17:31
  • $\begingroup$ from the tarjan survey cited by reza, basically the linear time algorithms perform very well/best for a moderate number of vertices/edges, and then there is a threshhold of larger vertices/edges where the logarithmic algorithms outperform the linear algorithm. so the logarithmic access fns are useful & may be significantly better for very large graphs. $\endgroup$
    – vzn
    Feb 5, 2013 at 22:29

2 Answers 2

Reset to default
7
$\begingroup$

There is a paper titled "Dynamic Trees in Practice" which reviews the practical implementation.

The other categories that Link-Cut tree could be used efficiently is in Database Indexing. You can find this in the book "Database Index Techniques".

Improve this answer
$\endgroup$
3
  • $\begingroup$ think this needs some elaboration. trees are useful for indexes in general of course but under what conditions would the tree be modified? $\endgroup$
    – vzn
    Feb 5, 2013 at 22:35
  • $\begingroup$ @vzn: B+-tree, R-tree, H-Tree and X-Tree are some examples. $\endgroup$
    – Reza
    Feb 5, 2013 at 23:05
  • $\begingroup$ of course, but suspect maybe nobody has tried using link-cut trees in DB indexes to date. its a plausible app but it doesnt seem clear that they're optimized for the same operations that occur in DB indexes. $\endgroup$
    – vzn
    Feb 5, 2013 at 23:28
5
$\begingroup$

this paper finds at the end that a link-cut (LC) tree outperforms rake-compress (RC) trees for the Sleator/Tarjan max-flow algorithm using a standard Dimacs random graph generator.

the paper focuses on change propagation as one application of dynamic trees. eg, change propagation is similar to the way that excel spreadsheet cells have to be recomputed on changes to some cells based on cell/formula dependencies. the authors released their code as an open library.

An experimental analysis of change propagation in dynamic trees Acar, Blelloch, Vittes

Change propagation is a technique for automatically adjusting the output of an algorithm to changes in the input. The idea behind change propagation is to track the dependencies between data and function calls, so that, when the input changes, functions affected by that change can be re-executed to update the computation and the output. Change propagation makes it possible for a compiler to dynamize static algorithms.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. It's nice to see some benchmarks of algorithms involving dynamic trees. $\endgroup$
    – Rob Lachlan
    Feb 6, 2013 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.