Finding Disjoint Routes in Telecommunications Networks with Two Technologies

Anne de Jongh, Michel Gendreau and Martine Labbé
Additional contact information
Anne de Jongh: Université Libre de Bruxelles, Bruxelles, Belgium
Michel Gendreau: Université de Montréal, Montréal, Québec, Canada
Martine Labbé: Université Libre de Bruxelles, Bruxelles, Belgium

Operations Research, 1999, vol. 47, issue 1, 81-92

Abstract: We consider networks in which a cost is associated with each arc or edge and a transition cost is associated with each node. This last cost is related to the presence of two technologies on the network and is incurred only when a flow enters and leaves the corresponding node on arcs of different types. The problem we consider consists in finding two node disjoint paths with minimum total cost. We show that it is strongly NP-complete. Then we propose two heuristics, study their worst case behavior, provide a lower bounding procedure based on Lagrangean relaxation, and finally embed those elements in a branch and bound procedure.

Keywords: communications; telecommunications networks; network/graphs; flow algorithms; disjoint paths; programming; integer; algorithm for bifurcated routing with transition costs (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.1.81 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:47:y:1999:i:1:p:81-92

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().