On the complexity of quality of service routing

被引：27

作者：

Wang, Z ^{[1
]}

机构：

[1] AT&T Bell Labs, Lucent Technol, High Speed Networks Dept, Holmdel, NJ 07733 USA

来源：

INFORMATION PROCESSING LETTERS | 1999年 / 69卷 / 03期

关键词：

computational complexity; NP-completeness; routing; shortest path; multiple constraints;

D O I：

10.1016/S0020-0190(98)00206-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

One of the basic problems in quality of service (QoS) routing is to find a path subject to multiple constraints on routing metrics. We first show that for additive and multiplicative metrics, the path finding problem is NP-complete, and then apply the results to QoS routing. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：111 / 114

页数：4