On the efficiency of maximum-flow algorithms on networks with small integer capacities

DOI10.1007/BF01553885zbMath0657.90037MaRDI QIDQ1111460

Charles U. Martel, David Fernández Baca

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

upper boundtotal potentialmaximum subgraph density problemmaximum-flow algorithmsnumber of phases

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items (2)

Maximum flow problem in wireless ad hoc networks with directional antennas ⋮ AO(nm log(U/n)) time maximum flow algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• A data structure for dynamic trees
• Fast Algorithms for Bipartite Network Flow
• Computational Comparison of Eight Methods for the Maximum Network Flow Problem
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Selected Applications of Minimum Cuts in Networks
• Network Flow and Testing Graph Connectivity

This page was built for publication: On the efficiency of maximum-flow algorithms on networks with small integer capacities