Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search

DOI10.1007/978-3-662-48350-3_52zbMath1466.68091OpenAlexW2294178601MaRDI QIDQ3452823

Haim Kaplan, Renato F. Werneck, Sagi Hed, Andrew V. Goldberg, Pushmeet Kohli, Robert Endre Tarjan

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48350-3_52

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Enhanced instance space analysis for the maximum flow problem

Uses Software

• MAXFLOW

Cites Work

• On implementing the push-relabel method for the maximum flow problem
• Better Bounds for Graph Bisection
• Maximum Flows by Incremental Breadth-First Search
• Maximal Flow Through a Network
• The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem
• The Partial Augment–Relabel Algorithm for the Maximum Flow Problem
• A new approach to the maximum-flow problem
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem