[ACM Press the Second Symposium - Hanoi, Vietnam (2011.10.13-2011.10.14)] Proceedings of the Second Symposium on Information and Communication Technology - SoICT '11 - A routing algorithm of pairwise disjoint paths in a burnt pancake graph

✍ Scribed by Iwasaki, Tatsuya; Kaneko, Keiichi

• Book ID: 121231594
• Publisher: ACM Press
• Year: 2011
• Weight: 587 KB
• Category: Article
• ISBN: 1450308805
• DOI: 10.1145/2069216.2069232

✦ Synopsis

In this paper, we propose an algorithm that solves the kpariwise disjoint path problem in an n-burnt pancake graph where n ≥ 4 and k = n/2 in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n 3 ) and the maximum path length 2n + 9.