## Abstract

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 language | English |
---|---|

Pages (from-to) | 465-471 |

Number of pages | 7 |

Journal | IEICE Transactions on Information and Systems |

Volume | E90-D |

Issue number | 2 |

DOIs | |

Publication status | Published - Feb 2007 |

Externally published | Yes |

## Keywords

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