A LINEAR TIME ALGORITHM FOR THE MAXIMUM CAPACITY PATH PROBLEM

被引：41

作者：

PUNNEN, AP ^{[1
]}

机构：

[1] INDIAN INST TECHNOL,DEPT MATH,KANPUR 208016,UTTAR PRADESH,INDIA

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1991年 / 53卷 / 03期

关键词：

NETWORKS; SHORTEST PATHS; MAXMIN PATHS; LINEAR TIME ALGORITHM; COMPUTATIONAL COMPLEXITY;

D O I：

10.1016/0377-2217(91)90073-5

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：402 / 404

页数：3