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+nlogn, mlogÅnW}). where m is the number of edges, n is the number of vertices and W is the maximum edge capacity. The paper gives a simple O(m) algorithm to solve this problem. A by-product of this result is an O(m’2) algorithm for a bicriteria path problem which is an improvement over the available O(m²logn) algorithm.