patternMinor
Are link-cut trees ever used in practice, for max flow computation or other applications?
Viewed 0 times
flowcomputationareusedpracticecutapplicationstreesmaxfor
Problem
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).
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?
- 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?
Solution
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".
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".
Context
StackExchange Computer Science Q#9501, answer score: 7
Revisions (0)
No revisions yet.