Finding minimum-cost paths with minimum sharability

被引：5

作者：

Zheng, S. Q. ^{[1
]}

Yang, Bing ^{[2
]}

Yang, Mei ^{[3
]}

Wang, Jianping ^{[1
]}

机构：

[1] Univ Texas, Dept Comp Sci, Richardson, TX 75083 USA

[2] Cisco Syst, Richardson, TX 75082 USA

[3] Univ Nevada, Dept Elect & Comp Engn, Las Vegas, NV 89154 USA

来源：

INFOCOM 2007, VOLS 1-5 | 2007年

关键词：

network; graph; routing; network planning; protocol; algorithm; protection; reliability; survivability; disjoint paths; multiple paths; network flow; complexity;

D O I：

10.1109/INFCOM.2007.180

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

In communication networks, multiple communication paths sharing minimum number of links or/and nodes may be desirable for improved performance, resource utilization and reliability. We introduce the notion of link sharability and node sharability, and consider the problems of finding minimum-cost k paths subject to minimum link/node sharability constraints. We identify 65 different link/node sharability constraints, and consider the fundamental problem of finding minimum-cost k paths between a pair of nodes under these constraints. We present a unified polynomial-time algorithm scheme for solving this problem subject to 25 of these different sharability constraints.

引用

页码：1532 / +

页数：3