IEICE TRANSACTIONS on Information
An Algorithm for Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs
Summary :
A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm.
- Publication
- IEICE TRANSACTIONS on Information Vol.E86-D No.12 pp.2588-2594
- Publication Date
- 2003/12/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Dependable Computing)
- Category
- Dependable Communication
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, "An Algorithm for Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs" in IEICE TRANSACTIONS on Information,
vol. E86-D, no. 12, pp. 2588-2594, December 2003, doi: .
Abstract: A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_12_2588/_p
Copy
@ARTICLE{e86-d_12_2588,
author={Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={An Algorithm for Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs},
year={2003},
volume={E86-D},
number={12},
pages={2588-2594},
abstract={A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm.},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - An Algorithm for Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 2588
EP - 2594
AU - Keiichi KANEKO
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2003
AB - A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm.
ER -
English
