Computational Comparison of Eight Methods for the Maximum Network Flow Problem

DOI10.1145/355873.355874zbMath0432.90071OpenAlexW2078206222MaRDI QIDQ3870686

To-yat Cheung

Publication date: 1980

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/355873.355874

zbMATH Keywords

depth-first searchcomparison of algorithmsbreadth-first searchDinic algorithmKarzanov algorithmmaximum network flow problemcomputational comparison of eight methodsflow augmentation along pathsflow augmentation through layersKinariwala-Rao algorithmlargest-augmentationlayer- updating

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (6)

On the efficiency of maximum-flow algorithms on networks with small integer capacities ⋮ Enhanced instance space analysis for the maximum flow problem ⋮ An extended abstract of an indepth algorithmic and computational study for maximum flow problems ⋮ Linear dynamics for the state vector of Markov chain functions ⋮ Computational investigations of maximum flow algorithms ⋮ Implementing Goldberg's max-flow-algorithm ? A computational investigation

This page was built for publication: Computational Comparison of Eight Methods for the Maximum Network Flow Problem