Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
overview/desc of link cut trees but only states "is useful for applications such as Network Flow" –  vzn Feb 5 '13 at 17:31
    
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. –  vzn Feb 5 '13 at 22:29
add comment

2 Answers

up vote 4 down vote accepted

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".

share|improve this answer
    
Thank you, that's an excellent reference. –  Rob Lachlan Feb 5 '13 at 22:26
    
think this needs some elaboration. trees are useful for indexes in general of course but under what conditions would the tree be modified? –  vzn Feb 5 '13 at 22:35
    
@vzn: B+-tree, R-tree, H-Tree and X-Tree are some examples. –  Reza Feb 5 '13 at 23:05
    
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. –  vzn Feb 5 '13 at 23:28
add comment

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.

share|improve this answer
    
Thank you. It's nice to see some benchmarks of algorithms involving dynamic trees. –  Rob Lachlan Feb 6 '13 at 7:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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