A constrained capacity expansion problem on networks

被引：19

作者：

Yang, C ^{[1
]}

Zhang, JZ ^{[1
]}

机构：

[1] City Univ Hong Kong, Dept Math, Hong Kong, Hong Kong

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 1998年 / 70卷 / 01期

关键词：

networks and graphs; maximum capacity path; spanning tree; polynomial algorithm;

D O I：

10.1080/00207169808804733

中图分类号：

O29 [应用数学];

学科分类号：

070104 [应用数学];

摘要：

In this paper we consider a type of constrained maximum capacity path (CMCP) problem which can be described as how to increase the capacity vector of a network so that the capacities of the maximum capacity path for every pair of nodes in the network can be increased to the maximum extent while the total cost for the increment of capacity is within a given budget limit. We transform this problem into solving some minimum spanning tree problems and propose a strongly polynomial algorithm for this problem. Finally we discuss other methods and show the advantage of the proposed algorithm.

引用

页码：19 / 33

页数：15