A generalization of the scaling max-flow algorithm

DOI10.1016/S0305-0548(03)00171-0MaRDI QIDQ1885993zbMATH OpenOpenAlexFDO

Authors Sergio Alonso, Antonio Sedeño-Noda, C. González-Martín

Publication date 12 November 2004

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0305-0548(03)00171-0

zbMATH Keywords

Worst-case complexityComputational experimentMaximum flow problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic network models in operations research (90B10) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 1187161
• Improved Time Bounds for the Maximum Flow Problem
• A strongly polynomial algorithm for generalized flow maximization
• A Fast and Simple Algorithm for the Maximum Flow Problem
• A capacity scaling algorithm for the constrained maximum flow problem

Cites work

• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• A Fast and Simple Algorithm for the Maximum Flow Problem
• A Faster Deterministic Maximum Flow Algorithm
• A data structure for dynamic trees
• AO(nm log(U/n)) time maximum flow algorithm
• An $o(n^3 )$-Time Maximum-Flow Algorithm
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• An algorithmic study of the maximum flow problem: A comparative statistical analysis
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Beyond the flow decomposition barrier
• Computational investigations of maximum flow algorithms
• Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems
• Implementing Goldberg's max-flow-algorithm ? A computational investigation
• Improved Time Bounds for the Maximum Flow Problem
• Maximal Flow Through a Network
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Network flows. Theory, algorithms, and applications.
• On implementing the push-relabel method for the maximum flow problem
• Scaling algorithms for network problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(7)

• scientific article; zbMATH DE number 1869742 (Why is no real title available?)
• Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
• scientific article; zbMATH DE number 1187161 (Why is no real title available?)
• scientific article; zbMATH DE number 176498 (Why is no real title available?)
• A computational study of the capacity scaling algorithm for the maximum flow problem
• scientific article; zbMATH DE number 2086656 (Why is no real title available?)
• A capacity scaling algorithm for the constrained maximum flow problem

Describes a project that uses

Uses Software

• LEDA
• NETGEN

This page was built for publication: A generalization of the scaling max-flow algorithm

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