A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
From MaRDI portal
Publication:6139374
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
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 2 (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 ℓ 1 -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