Bottleneck flows in networks

Details Bottleneck flows in networks Bottleneck flows in networks

2007-12-22

arxiv.org/abs/0712.3858v1

Computer Science

Data Structures and Algorithms

Scientific paper

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. In this paper we provide a review of important results on this topic and its various special cases. We observe that the BNFP can be solved as a sequence of $O(\log n)$ maximum flow problems. However, special augmenting path based algorithms for the maximum flow problem can be modified to obtain algorithms for the BNFP with the property that these variations and the corresponding maximum flow algorithms have identical worst case time complexity. On unit capacity network we show that BNFP can be solved in $O(\min \{{m(n\log n)}^{{2/3}}, m^{{3/2}}\sqrt{\log n}\})$. This improves the best available algorithm by a factor of $\sqrt{\log n}$. On unit capacity simple graphs, we show that BNFP can be solved in $O(m \sqrt {n \log n})$ time. As a consequence we have an $O(m \sqrt {n \log n})$ algorithm for the BTP with unit arc capacities.

Affiliated with

Also associated with

No associations

Rating

Bottleneck flows in networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bottleneck flows in networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bottleneck flows in networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-425964