Set-to-Set Disjoint Paths Routing in Pancake Graphs

S. Peng and K. Kaneko (Japan)


disjoint paths, interconnection networks, routing algorithm


In this paper, we propose an efficient algorithm that finds disjoint paths for set-to-set routing in pancake graphs. For an n-pancake graph, the algorithm can find n − 1 disjoint paths of small maximum length with optimal time com plexity. That is, the n−1 paths can be constructed in O(n2 ) time and the maximum length is bounded by 5n/3 + O(1).

Important Links:

Go Back