On the complexity of quality of service routing
12 February 1999
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.