An Algorithm for Node-Disjoint Paths in Pancake Graphs
Yasuto Suzuki, Keiichi Kaneko · IEICE Transactions on Information and Systems · 2003
SUMMARY For any pair of distinct nodes in an n-pancake graph, we give an algorithm for construction of n � 1 internally disjoint paths connecting the nodes in the time complexity of polynomial order of n. The length of each path obtained and the time complexity of the algorithm are estimated theoretically and verified by computer simulation.