HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are link-cut trees ever used in practice, for max flow computation or other applications?

Submitted by: @import:stackexchange-cs··
0
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).

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

Context

StackExchange Computer Science Q#9501, answer score: 7

Revisions (0)

No revisions yet.