A survey on exact algorithms for the maximum flow and minimum‐cost flow problems

DOI10.1002/net.22169zbMath1529.90064OpenAlexW4381333972MaRDI QIDQ6139374

Unnamed Author, Adam N. Letchford

Publication date: 18 December 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.22169

zbMATH Keywords

combinatorial optimizationnetwork flows

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Flows in graphs (05C21)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating pseudo-random permutations and maximum flow algorithms
• A strongly polynomial minimum cost circulation algorithm
• An \(O(EV\log^2V)\) algorithm for the maximal flow problem
• An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem
• Finding minimum-cost flows by double scaling
• Computational investigations of maximum flow algorithms
• On implementing the push-relabel method for the maximum flow problem
• On-line load balancing and network flow
• A data structure for dynamic trees
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The Transhipment Problem
• Minimum-cost flow algorithms: an experimental evaluation
• A Fast and Simple Algorithm for the Maximum Flow Problem
• Beyond the flow decomposition barrier
• Maximal Flow Through a Network
• Monotone networks
• Finding Minimum-Cost Circulations by Successive Approximation
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• An O (n ² (m + N log n )log n ) min-cost flow algorithm
• A new approach to the maximum-flow problem
• Improved Time Bounds for the Maximum Flow Problem
• An Out-of-Kilter Method for Minimal-Cost Flow Problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A Faster Deterministic Maximum Flow Algorithm
• Faster Scaling Algorithms for Network Problems
• Faster energy maximization for faster maximum flow
• A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem
• Online load balancing and network flow
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• On the History of Combinatorial Optimization (Till 1960)
• Network Flow Algorithms
• Max flows in O(nm) time, or better
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• On some techniques useful for solution of transportation network problems
• An $o(n^3 )$-Time Maximum-Flow Algorithm
• Combinatorial optimization. Theory and algorithms
• Integer priority queues with decrease key in constant time and the single source shortest paths problem
• Minimum cost flows, MDPs, and ℓ ₁ -regression in nearly linear time for dense instances

This page was built for publication: A survey on exact algorithms for the maximum flow and minimum‐cost flow problems