Disjoint Paths Routing in Pancake Graphs
Keiichi Kaneko, Shietung Peng · 2006
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