Simplifying maximum flow computations: the effect of shrinking and good initial flows

DOI10.1016/J.DAM.2011.06.030MaRDI QIDQ411873zbMATH OpenOpenAlexFDO

Authors G. Pardella, F. Liers

Publication date 30 April 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.06.030

zbMATH Keywords

hybrid algorithmmaximum flowminimum cutflow-conserving conditionsmaximum flow algorithmssubgraph contractionsubgraph shrinkingtwo-step max-flow algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Flows in graphs (05C21)

Recommendations

• scientific article; zbMATH DE number 1759406
• TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration
• A new approach to the maximum-flow problem
• The maximum flow problem: A max-preflow approach
• Computing and Combinatorics

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A new approach to the maximum-flow problem
• An efficient algorithm for the minimum capacity cut problem
• Maximal Flow Through a Network
• Network flows. Theory, algorithms, and applications.
• Practical performance of efficient minimum cut algorithms
• The Partial Augment–Relabel Algorithm for the Maximum Flow Problem
• The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(7)

• scientific article; zbMATH DE number 1759406 (Why is no real title available?)
• TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration
• Maximum flows by incremental breadth-first search
• Parallel computing of Edwards-Anderson model
• An integrated rolling horizon and adaptive-refinement approach for disjoint trajectories optimization
• An optimal pruned traversal tree-based fast minimum cut solver in dense graph
• scientific article; zbMATH DE number 2086656 (Why is no real title available?)

Describes a project that uses

Uses Software

• Rudy
• MAXFLOW
• OGDF

This page was built for publication: Simplifying maximum flow computations: the effect of shrinking and good initial flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q411873)