On the efficiency of maximum-flow algorithms on networks with small integer capacities (Q1111460)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the efficiency of maximum-flow algorithms on networks with small integer capacities |
scientific article |
Statements
On the efficiency of maximum-flow algorithms on networks with small integer capacities (English)
0 references
1989
0 references
The performance of maximum-flow algorithms that work in phases is studied as a function of the maximum arc capacity, C, of the network and a quantity we call the total potential, P, of the network, which is related to the average amount of flow that can be sent through a node. Extending results by \textit{S. Even} and \textit{R. E. Tarjan} [SIAM J. Computing 4, 507-518 (1975; Zbl 0328.90031)] we derive a tight \(O(\min \{C^{1/3}| V|^{2/3},P^{1/2},| V| \})\) upper bound on the number of phases. An O(min\(\{\) P log\(| V|,C| V|^{3/2},| V|^ 2| E| \})\) upper bound is derived on the total length of the augmenting paths used by Dinic's algorithm. The latter quantity is useful in estimating the performance of Dinic's method on certain inputs. Our results show that on a natural class of networks, the performance of Dinic's algorithm is significantly better than would be apparent from a bound based on \(| V|\) and \(| E|\) alone. We present an application of our bounds to the maximum subgraph density problem.
0 references
maximum-flow algorithms
0 references
total potential
0 references
number of phases
0 references
upper bound
0 references
maximum subgraph density problem
0 references
0 references