On implementing push-relabel method for the maximum flow problem

DOI10.1007/3-540-59408-6_49zbMath1498.90237OpenAlexW1685122025WikidataQ57407475 ScholiaQ57407475MaRDI QIDQ5101413

Andrew V. Goldberg, Boris V. Cherkassky

Publication date: 30 August 2022

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59408-6_49

zbMATH Keywords

speedupcombination of heuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

A Benders decomposition based framework for solving cable trench problems ⋮ TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration ⋮ Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems ⋮ Vertex covering with capacitated trees ⋮ Exact Approaches for Network Design Problems with Relays ⋮ Mixed-integer programming approaches for the time-constrained maximal covering routing problem ⋮ Solving minimum-cost shared arborescence problems ⋮ A two-phase greedy algorithm to locate and allocate hubs for fixed-wireless broadband access ⋮ Plant location with minimum inventory ⋮ Mixed-integer programming approaches for the tree \(t^*\)-spanner problem

Uses Software

• DIMACS

Cites Work

• DIMACS
• A simple version of Karzanov's blocking flow algorithm
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• A new approach to the maximum-flow problem
• Improved Time Bounds for the Maximum Flow Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Implementing Goldberg's max-flow-algorithm ? A computational investigation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item