The maximum flow problem: A max-preflow approach

DOI10.1016/0377-2217(91)90060-9MaRDI QIDQ811325zbMATH OpenOpenAlexFDO

Authors Guiseppe Mazzoni, Stefano Pallottino, Maria Grazia Scutellà

Publication date 1991

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(91)90060-9

zbMATH Keywords

flow push pathsmaximum preflow

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Recommendations

• A new approach to the maximum-flow problem
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• scientific article; zbMATH DE number 4079142
• scientific article; zbMATH DE number 176469
• A new Karzanov-type O(n^ 3) max-flow algorithm

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 193993 (Why is no real title available?)
• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (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 data structure for dynamic trees
• A new approach to the maximum-flow problem
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n^ 2m) time
• A simple version of Karzanov's blocking flow algorithm
• An O(n2log n) parallel max-flow algorithm
• An \(O(EV\log^2V)\) algorithm for the maximal flow problem
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems
• Dual coordinate step methods for linear network flow problems
• Implementing Goldberg's max-flow-algorithm ? A computational investigation
• Improved Time Bounds for the Maximum Flow Problem
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Scaling algorithms for network problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(15)

• Playing with the Maximum-Flow Problem
• Simplifying maximum flow computations: the effect of shrinking and good initial flows
• An analysis of the highest-level selection rule in the preflow-push max-flow algorithm
• scientific article; zbMATH DE number 176469 (Why is no real title available?)
• The maximum flow problem with disjunctive constraints
• Efficient preflow push algorithms
• The Maximum Flow Problem for Oriented Flows
• PRACTICAL EFFICIENCY OF MAXIMUM FLOW ALGORITHMS USING MA ORDERINGS AND PREFLOWS
• Computational investigations of maximum flow algorithms
• A new approach to computing maximum flows using electrical flows
• scientific article; zbMATH DE number 515924 (Why is no real title available?)
• scientific article; zbMATH DE number 6863577 (Why is no real title available?)
• The maximum flow problem of uncertain network
• A new approach to the maximum-flow problem
• An auction algorithm for the max-flow problem

Describes a project that uses

Uses Software

• NETGEN

This page was built for publication: The maximum flow problem: A max-preflow approach

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