Abstract
In telecommunication networks design the problem of obtaining optimal (arc or node) disjoint paths, for increasing network reliability, is extremely important. The problem of calculating k c disjoint paths from s to t (two distinct nodes), in a network with k c different (arbitrary) costs on every arc such that the total cost of the paths is minimised, is NP-complete even for k c =2. When k c =2 these networks are usually designated as dual arc cost networks.
In this paper we propose an exact algorithm for finding the whole set of arc-disjoint path pairs, with minimal cost in a network with dual arc costs. The correctness of the algorithm is based on a condition which guarantees that the optimal path pair cost has been obtained and on a proposition which guarantees that at the end of the algorithm all the optimal pairs have been obtained. The optimality condition is based on the calculation of upper and lower bounds on the optimal cost. Extensive experimentation is presented to show the effectiveness of the algorithm.
Similar content being viewed by others
References
Bang-Jensen J, Gutin G (2002) Digraphs: theory, algorithms and applications. Springer monographs in mathematics. Springer, Berlin
Bhandari R (1999) Survivable networks, algorithms for diverse routing. Kluwer Academic, Norwell
Ford LR Jr, Fulkerson DR (1962) Network flows. Princeton University Press, Princeton
Fredman ML, Tarjan RE (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J Assoc Comput Mach 34:596–615
Gomes T, Martins L, Craveirinha J (2001) An algorithm for calculating the k shortest paths with a maximum number of arcs. Investig Oper 21(2):235–244
Gomes T, Craveirinha J, Jorge L (2009) An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs. Comput Oper Res 36(5):1670–1682
Ho PH, Tapolcai J, Cinkler T (2004a) Segment shared protection in mesh communications networks with bandwidth guaranteed tunnels. IEEE/ACM Trans Netw 12(16):1105–1118
Ho PH, Tapolcai J, Mouftah HT (2004b) On achieving optimal survivable routing for shared protection in survivable next-generation Internet. IEEE Trans Reliability 53(2):216–225
Kodialam M, Lakshman TV (2003) Dynamic routing of restorable bandwidth-guaranteed tunnels using aggregated network resource usage information. IEEE/ACM Trans Netw 11(3):399–410
Laborczi P, Tapolcai J, Ho PH, Cinkler T, Recski A, Mouftah HT (2001) Algorithms for asymmetrically weighted pair of disjoint paths in survivable networks. In: Cinkler, T. (ed) Proceedings of design of reliable communication networks (DCRN 2001), pp 220–227
Li CL, McCormick ST, Simchi-Levi D (1992) Finding disjoint paths with different path costs: complexity and algorithms. Networks 22:653–667
Martins E, Pascoal M (2003) A new implementation of Yen’s ranking loopless paths algorithm. 4OR 1(2):121–134
Martins E, Pascoal M, Santos J (1999a) An algorithm for ranking loopless paths. Technical Report 99/007, CISUC (1999). http://www.mat.uc.pt/~marta/Publicacoes/mps2.ps
Martins E, Pascoal M, Santos J (1999b) Deviation algorithms for ranking shortest paths. Int J Found Comput Sci 10(3):247–263
Mouftah HT, Ho PH (2003) Optical networks—architecture and survivability. Kluwer Academic, Norwell
Suurballe JW (1974) Disjoint paths in networks. Networks 4:125–145
Suurballe JW, Tarjan RE (1984) A quick method for finding shortest pairs of disjoint paths. Networks 14(2):325–336
Xu D, Chen Y, Xiong Y, Qiao C, He X (2004) On finding disjoint paths in single and dual link cost networks. In: EEE INFOCOM 2004. IEEE Press, New York
Yen JY (1971) Finding the k shortest loopless paths in a network. Manag Sci 17(11):712–716
Author information
Authors and Affiliations
Corresponding author
Additional information
Work partially supported by programme POSC of the EC programme cosponsored by national funds.
Rights and permissions
About this article
Cite this article
Gomes, T., Craveirinha, J. & Jorge, L. An effective algorithm for obtaining the whole set of minimal cost pairs of disjoint paths with dual arc costs. J Comb Optim 19, 394–414 (2010). https://doi.org/10.1007/s10878-009-9255-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-009-9255-4