Recent developments in maximum flow algorithms

DOI10.1007/BFB0054350MaRDI QIDQ5054836zbMATH OpenFDO

Authors Andrew V. Goldberg

Publication date 9 December 2022

Published in Algorithm Theory — SWAT'98 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0054350

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Cites work

• A combinatorial interior point method for network flow problems
• A data structure for dynamic trees
• A Fast and Simple Algorithm for the Maximum Flow Problem
• A Faster Deterministic Maximum Flow Algorithm
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A new approach to the maximum-flow problem
• A new approach to the minimum cut problem
• A Randomized Maximum-Flow Algorithm
• An o(n^3 )-Time Maximum-Flow Algorithm
• An \(O(EV\log^2V)\) algorithm for the maximal flow problem
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Finding Minimum-Cost Circulations by Successive Approximation
• Generating pseudo-random permutations and maximum flow algorithms
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• scientific article; zbMATH DE number 1256719 (Why is no real title available?)
• scientific article; zbMATH DE number 1263226 (Why is no real title available?)
• scientific article; zbMATH DE number 1303591 (Why is no real title available?)
• scientific article; zbMATH DE number 515922 (Why is no real title available?)
• scientific article; zbMATH DE number 515923 (Why is no real title available?)
• scientific article; zbMATH DE number 1559539 (Why is no real title available?)
• scientific article; zbMATH DE number 1775390 (Why is no real title available?)
• scientific article; zbMATH DE number 742960 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• scientific article; zbMATH DE number 3069634 (Why is no real title available?)
• Implementing Goldberg's max-flow-algorithm ? A computational investigation
• Improved Time Bounds for the Maximum Flow Problem
• Maximal Flow Through a Network
• Minimum cuts and related problems
• Network Flow and Testing Graph Connectivity
• Network flows. Theory, algorithms, and applications.
• On implementing the push-relabel method for the maximum flow problem
• Online load balancing and network flow
• Random sampling in cut, flow, and network design problems
• Scaling algorithms for network problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(4)

• Algorithms for distributing telecommunication traffic on a multiple-ring SONET-based network.
• Clustering with partial information
• Risk‐averse optimization and resilient network flows
• Estimation of mean dynamic outgoing network flow value

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Recent developments in maximum flow algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5054836)