Bottleneck flows in networks - Computer Science > Data Structures and AlgorithmsReportar como inadecuado

Bottleneck flows in networks - Computer Science > Data Structures and Algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: The bottleneck network flow problem BNFP is a generalization of severalwell-studied bottleneck problems such as the bottleneck transportation problemBTP, bottleneck assignment problem BAP, bottleneck path problem BPP, andso on. In this paper we provide a review of important results on this topic andits various special cases. We observe that the BNFP can be solved as a sequenceof $O\log n$ maximum flow problems. However, special augmenting path basedalgorithms for the maximum flow problem can be modified to obtain algorithmsfor the BNFP with the property that these variations and the correspondingmaximum flow algorithms have identical worst case time complexity. On unitcapacity network we show that BNFP can be solved in $O\min \{{mn\logn}^{{2-3}}, m^{{3-2}}\sqrt{\log n}\}$. This improves the best availablealgorithm by a factor of $\sqrt{\log n}$. On unit capacity simple graphs, weshow that BNFP can be solved in $Om \sqrt {n \log n}$ time. As a consequencewe have an $Om \sqrt {n \log n}$ algorithm for the BTP with unit arccapacities.

Autor: Abraham P. Punnen, Ruonan Zhang


Documentos relacionados