Variants of the Min-Sum Link-Disjoint Paths Problem

Title

Variants of the Min-Sum Link-Disjoint Paths Problem

 Author

Beshir, A.A.
Kuipers, F.A.

Faculty

Electrical Engineering, Mathematics and Computer Science

 Department

Network Architectures and Services

 Date

2009-11-19

 Abstract

A survivable connection usually requires computing link-disjoint primary and backup paths. Finding a min-sum pair of link-disjoint paths whose total cost is minimized can be solved in polynomial time. However, adding extra requirements may render the problem NP-complete. In this paper, we study different variants of the min-sum link-disjoint paths problem. We examine the complexity of these problem variants and provide exact and heuristic algorithms for them.

 To reference this document use:

http://resolver.tudelft.nl/uuid:b81f6a15-b7a6-4cc6-a464-9fedbda0960b

 Publisher

IEEE/SCVT

 Source

16th Annual Symposium on Communications and Vehicular Technology in the Benelux (SCVT 2009), November 19, 2009

 Part of collection

Institutional Repository

 Document type

conference paper

 Rights

(c) 2009 Beshir, A.A., Kuipers, F.A.
Files
PDF scvtpaper.pdf 141.52 KB
Close viewer