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

DOI10.1016/j.dam.2011.06.030zbMath1250.05053OpenAlexW1984627379MaRDI QIDQ411873

G. Pardella, Frauke 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

minimum cutmaximum flowhybrid algorithmflow-conserving conditionsmaximum flow algorithmssubgraph contractionsubgraph shrinkingtwo-step max-flow algorithm

Mathematics Subject Classification ID

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

Related Items (4)

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

Uses Software

• OGDF
• MAXFLOW
• Rudy

Cites Work

• Unnamed Item
• Unnamed Item
• The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate
• An efficient algorithm for the minimum capacity cut problem
• Practical performance of efficient minimum cut algorithms
• Maximal Flow Through a Network
• The Partial Augment–Relabel Algorithm for the Maximum Flow Problem
• A new approach to the maximum-flow problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

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