DocumentCode :
1991184
Title :
An Efficient Disjoint Shortest Paths Routing Algorithm for the Hypercube
Author :
Qiu, Ke
Author_Institution :
Dept. of Comput. Sci., Brock Univ., St. Catharines, ON, Canada
fYear :
2008
fDate :
8-10 Dec. 2008
Firstpage :
43
Lastpage :
47
Abstract :
We present a routing algorithm that finds n disjoint shortest paths from the source node to n target nodes in the n-dimensional hypercube in O(n3log n)=O(log3NloglogN) time, where N=2n, provided that such disjoint shortest paths exist which can be checked in O(n5/2) time, improving the previous O(n4) routing algorithm.
Keywords :
computational complexity; hypercube networks; network routing; disjoint shortest paths routing algorithm; n-dimensional hypercube; source node; target nodes; Algorithm design and analysis; Computer science; Fault tolerance; Hamming weight; Hypercubes; Multiprocessor interconnection networks; Routing; Sufficient conditions;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Systems, 2008. ICPADS '08. 14th IEEE International Conference on
Conference_Location :
Melbourne, VIC
ISSN :
1521-9097
Print_ISBN :
978-0-7695-3434-3
Type :
conf
DOI :
10.1109/ICPADS.2008.119
Filename :
4724301
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=1991184
بازگشت