Title :
Disjoint Paths Routing in Pancake Graphs
Author :
Kaneko, Keiichi ; Peng, Shietung
Author_Institution :
Tokyo Univ. of Agric. & Technol.
Abstract :
In this paper, we propose efficient algorithms that find disjoint paths for node-to-node and node-to-set routing in pancake graphs. For an n-pancake graph, the algorithms can find n - 1 disjoint paths of small maximum length with optimal time complexity. That is, the n - 1 paths can be constructed in O(n2) time and the maximum length is bounded by 5n/3 + 6
Keywords :
computational complexity; graph theory; disjoint path routing; node-to-node routing; node-to-set routing; optimal time complexity; pancake graphs; Agricultural engineering; Agriculture; Algorithm design and analysis; Computer networks; Computer science; Concurrent computing; Hypercubes; Multiprocessor interconnection networks; Network topology; Routing;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2006. PDCAT '06. Seventh International Conference on
Conference_Location :
Taipei
Print_ISBN :
0-7695-2736-1
DOI :
10.1109/PDCAT.2006.56
