Bottleneck flows in unit capacity networks |
| |
Authors: | Abraham P Punnen Ruonan Zhang |
| |
Affiliation: | Department of Mathematics, Simon Fraser University Surrey, Central City, 250-13450 102nd AV, Surrey, British Columbia, V3T 0A3, Canada |
| |
Abstract: | The bottleneck network flow problem (BNFP) is a generalization of several well-studied bottleneck problems such as the bottleneck transportation problem (BTP), bottleneck assignment problem (BAP), bottleneck path problem (BPP), and so on. The BNFP can easily be solved as a sequence of O(logn) maximum flow problems on almost unit capacity networks. We observe that this algorithm runs in O(min{m3/2,n2/3m}logn) time by showing that the maximum flow problem on an almost unit capacity graph can be solved in O(min{m3/2,n2/3m}) time. We then propose a faster algorithm to solve the unit capacity BNFP in time, an improvement by a factor of at least . For dense graphs, the improvement is by a factor of . On unit capacity simple graphs, we show that BNFP can be solved in time, an improvement by a factor of . As a consequence we have an algorithm for the BTP with unit arc capacities. |
| |
Keywords: | Algorithms Combinatorial problems Graphs Network flows Minimum cost flow Unit capacity |
本文献已被 ScienceDirect 等数据库收录! |
|