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?