A new approximation algorithm for computing 2-restricted disjoint paths

Chao Peng, Hong Shen

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


In this paper we study the problem of how to identify multiple disjoint paths that have the minimum total cost OPT and satisfy a delay bound D in a graph G. This problem has lots of applications in networking such as fault-tolerant quality of service (QoS) routing and network-flow load balancing. Recently, several approximation algorithms have been developed for this problem. Here, we propose a new approximation algorithm for it by using the Lagrangian Relaxation method. We then present a simple approximation algorithm for finding multiple link-disjoint paths that satisfy the delay constraints at a reasonable total cost. If the optimal solution under delay-bound D has a cost OPT, then our algorithm can find a solution whose delay is bounded by (1+1/k)D and the cost is no more than (1+k)OPT. The time complexity of our algorithm is much better than the previous algorithms.

Original languageEnglish
Pages (from-to)465-471
Number of pages7
JournalIEICE Transactions on Information and Systems
Issue number2
Publication statusPublished - Feb 2007
Externally publishedYes


  • Approximation algorithms
  • Disjoint paths
  • Fault-tolerant routing
  • Lagrangian Relaxation


Dive into the research topics of 'A new approximation algorithm for computing 2-restricted disjoint paths'. Together they form a unique fingerprint.

Cite this