A LINEAR TIME ALGORITHM FOR THE MAXIMUM CAPACITY PATH PROBLEM

The maximum capacity path problem is to find a path joining two fixed vertices of an edge weighted graph such that the minimum edge weight is maximized. The best known algorithm to solve this problem has a worst-case complexity of O(min{m + n log n, m log(n)W}), where m is the number of edges, n is the number of vertices and W is the maximum edge capacity. We give a simple O(m) algorithm to solve this problem. As a by-product of this result, we have an O(m2) algorithm for a bicriteria path problem which is an improvement over the available O(m2log n) algorithm.