A generalization of the scaling max-flow algorithm

DOI10.1016/S0305-0548(03)00171-0zbMATH Open1068.68172OpenAlexW1976869646MaRDI QIDQ1885993FDOQ1885993

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

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

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)

Cites Work

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

Cited In (6)

• A capacity scaling algorithm for the constrained maximum flow problem
• Title not available (Why is that?)
• A computational study of the capacity scaling algorithm for the maximum flow problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost

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)