๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

[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
121231593
Publisher
ACM Press
Year
2011
Weight
587 KB
Category
Article
ISBN
1450308805

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

[ACM Press the Second Symposium - Hanoi,
[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
โœ Iwasaki, Tatsuya; Kaneko, Keiichi ๐Ÿ“‚ Article ๐Ÿ“… 2011 ๐Ÿ› ACM Press โš– 587 KB

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.