Computational investigations of maximum flow algorithms

DOI10.1016/S0377-2217(96)00269-XzbMath0920.90060OpenAlexW2051022544WikidataQ29028602 ScholiaQ29028602MaRDI QIDQ1278652

James B. Orlin, Murali Kodialam, Ajay K. Mishra, Ravindra K. Ahuja

Publication date: 22 February 1999

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

Full work available at URL: https://doi.org/10.1016/s0377-2217(96)00269-x

zbMATH Keywords

maximum flowcomputational comparisonsaugmenting path algorithmscapacity-scaling algorithmpreflow-push algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items (17)

A generalization of the scaling max-flow algorithm ⋮ An analysis of the highest-level selection rule in the preflow-push max-flow algorithm ⋮ Preemptive benchmarking problem: An approach for official statistics in small areas ⋮ Enhanced instance space analysis for the maximum flow problem ⋮ Simplifications and speedups of the pseudoflow algorithm ⋮ Assessing the reliability of a multistate logistics network under the transportation cost constraint ⋮ Networked dynamical systems 2016 ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Reachability cuts for the vehicle routing problem with time windows ⋮ Algorithms for distributing telecommunication traffic on a multiple-ring SONET-based network. ⋮ A minimal path-based method for computing multistate network reliability ⋮ Composability and controllability of structural linear time-invariant systems: distributed verification ⋮ Reliability evaluation of multi-state systems under cost consideration ⋮ A computational study of the capacity scaling algorithm for the maximum flow problem ⋮ A dynamic bounding algorithm for approximating multi-state two-terminal reliability ⋮ Efficient enumeration of \(d\)-minimal paths in reliability evaluation of multistate networks ⋮ An algorithmic study of the maximum flow problem: A comparative statistical analysis

Uses Software

• NETGEN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• The maximum flow problem: A max-preflow approach
• Generating pseudo-random permutations and maximum flow algorithms
• Scaling algorithms for network problems
• 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
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Numerical investigations on the maximal flow algorithm of Karzanov
• On implementing the push-relabel method for the maximum flow problem
• A data structure for dynamic trees
• An auction algorithm for the max-flow problem
• A Fast and Simple Algorithm for the Maximum Flow Problem
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Maximal Flow Through a Network
• A primal simplex variant for the maximum-flow problem
• A new approach to the maximum-flow problem
• Improved Time Bounds for the Maximum Flow Problem
• Computational Comparison of Eight Methods for the Maximum Network Flow Problem
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Toward a Programming Environment for Combinatorial Optimization: A Case Study Oriented to Max-Flow Computations
• Implementing Goldberg's max-flow-algorithm ? A computational investigation
• ON THE PRACTICAL EFFICIENCY OF VARIOUS MAXIMUM FLOW ALGORITHMS
• Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems
• Use of Representative Operation Counts in Computational Testing of Algorithms

This page was built for publication: Computational investigations of maximum flow algorithms