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

flow-conserving conditionshybrid algorithmmaximum flowmaximum flow algorithmsminimum cutsubgraph contractionsubgraph shrinkingtwo-step max-flow algorithm

Mathematics Subject Classification ID

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

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

• A new approach to the maximum-flow problem
• An efficient algorithm for the minimum capacity cut problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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

(8)

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

Describes a project that uses

Uses Software

• OGDF
• MAXFLOW
• Rudy

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)