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 complexity; max-flow problem; potential function arguments; reflow-push method

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

05C21: Flows in graphs

Related Items

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

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