Title :
An algorithm for the shortest pairs of arc-disjoint paths problem
Author :
Sun, Zhishuai ; Chen, Zhi ; Xie, Zheng ; Dai, Li
Author_Institution :
Sci. Sch., Nat. Univ. of Defense Technol., Changsha, China
Abstract :
Multipath Routing plays an important role in satellite network and computer communication network. It can increase the reliability of a network, avoid congestion and reduce the probability of dropped packets. The algorithm for finding shortest pairs of arc-disjoint paths is an important part of the multipath routing. In this paper, we first introduce the algorithm for the shortest pairs of arc-disjoint paths problem (SADPP) in networks which contain one sink with one source or several sources, then, we discuss the case in which we need to find the pairs of paths between any vertex and the sink. Finally, we present a method when the network is time-dependent.
Keywords :
computer networks; satellite communication; telecommunication network routing; arc-disjoint path problem; computer communication network; dropped packet; multipath routing; satellite network; shortest pair; Algorithm design and analysis; Complexity theory; Educational institutions; Heuristic algorithms; Linear programming; Routing; Satellites; algorithm; arc-disjoint; network; shortest paths;
Conference_Titel :
Natural Computation (ICNC), 2012 Eighth International Conference on
Conference_Location :
Chongqing
Print_ISBN :
978-1-4577-2130-4
DOI :
10.1109/ICNC.2012.6234600
