An analysis of the highest-level selection rule in the preflow-push max-flow algorithm

DOI10.1016/S0020-0190(99)00019-8zbMath1338.68097WikidataQ56018633 ScholiaQ56018633MaRDI QIDQ294662

Joseph Cheriyan, Kurt Mehlhorn

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019099000198?np=y

zbMATH Keywords

computational complexitymax-flow problempotential function argumentsreflow-push method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Flows in graphs (05C21)

Related Items (2)

Efficient preflow push algorithms ⋮ Rapidly computing robust minimum capacity s-t cuts: a case study in solving a sequence of maximum flow problems

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Computational investigations of maximum flow algorithms
• On the complexity of preflow-push algorithms for maximum-flow problems
• On implementing the push-relabel method for the maximum flow problem
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• A new approach to the maximum-flow problem

This page was built for publication: An analysis of the highest-level selection rule in the preflow-push max-flow algorithm