Improved Time Bounds for the Maximum Flow Problem (Classic Reprint): December 1987, Revised June 1988: December 1987, Revised June 1988 (Classic Reprint) - Softcover

Inhaltsangabe

New insights into fast maximum flow algorithms, with practical ideas for scaling and dynamic trees.

This work surveys improvements in time bounds for the maximum flow problem, focusing on the preflow framework and scaling techniques. It discusses how to move large amounts of flow quickly, and compares approaches that use careful vertex selection, scaling factors, and wave methods. The text also presents how dynamic trees can dramatically speed up computations by moving flow along paths instead of single arcs.

What you’ll experience
- A clear explanation of the preflow algorithm and its key constraints
- Details of scaling variants that aim to reduce total running time
- The use of dynamic trees to accelerate push operations and maintain structure
- Comparisons of different selection rules and their impact on performance

Ideal for readers of advanced algorithms, researchers, and students seeking a rigorous treatment of time bounds in network flow problems.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.