IEICE TRANSACTIONS on Information
An Algorithm for Node-to-Node Disjoint Paths Problem in Burnt Pancake Graphs
Summary :
In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-burnt pancake graphs in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n3) and the maximum path length 3n+4. We conducted a computer experiment for n=2 to 100 to measure the average performance of our algorithm. The results show that the average time complexity is O(n3.0) and the maximum path length is 3n+4.
- Publication
- IEICE TRANSACTIONS on Information Vol.E90-D No.1 pp.306-313
- Publication Date
- 2007/01/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- Type of Manuscript
- PAPER
- Category
- Dependable Computing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Keiichi KANEKO, Naoki SAWADA, "An Algorithm for Node-to-Node Disjoint Paths Problem in Burnt Pancake Graphs" in IEICE TRANSACTIONS on Information,
vol. E90-D, no. 1, pp. 306-313, January 2007, doi: .
Abstract: In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-burnt pancake graphs in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n3) and the maximum path length 3n+4. We conducted a computer experiment for n=2 to 100 to measure the average performance of our algorithm. The results show that the average time complexity is O(n3.0) and the maximum path length is 3n+4.
URL: https://global.ieice.org/en_transactions/information/10.1587/e90-d_1_306/_p
Copy
@ARTICLE{e90-d_1_306,
author={Keiichi KANEKO, Naoki SAWADA, },
journal={IEICE TRANSACTIONS on Information},
title={An Algorithm for Node-to-Node Disjoint Paths Problem in Burnt Pancake Graphs},
year={2007},
volume={E90-D},
number={1},
pages={306-313},
abstract={In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-burnt pancake graphs in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n3) and the maximum path length 3n+4. We conducted a computer experiment for n=2 to 100 to measure the average performance of our algorithm. The results show that the average time complexity is O(n3.0) and the maximum path length is 3n+4.},
keywords={},
doi={},
ISSN={1745-1361},
month={January},}
Copy
TY - JOUR
TI - An Algorithm for Node-to-Node Disjoint Paths Problem in Burnt Pancake Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 306
EP - 313
AU - Keiichi KANEKO
AU - Naoki SAWADA
PY - 2007
DO -
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2007
AB - In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-burnt pancake graphs in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n3) and the maximum path length 3n+4. We conducted a computer experiment for n=2 to 100 to measure the average performance of our algorithm. The results show that the average time complexity is O(n3.0) and the maximum path length is 3n+4.
ER -
English
