Node-to-Set Disjoint Paths Problem in Pancake Graphs
Summary :
In this paper, we give an algorithm for the node-to-set disjoint paths problem in pancake graphs with its evaluation results. The algorithm is of polynomial order of n for an n-pancake graph. It is based on recursion and divided into two cases according to the distribution of destination nodes in classes into which all the nodes in a pancake graph are categorized. The sum of lengths of paths obtained and the time complexity of the algorithm are estimated and the average performance is evaluated based on computer simulation.
- Publication
- IEICE TRANSACTIONS on Information Vol.E86-D No.9 pp.1628-1633
- Publication Date
- 2003/09/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Parallel and Distributed Computing, Applications and Technologies)
- Category
- Algorithms and Applications
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, Yasuto SUZUKI, "Node-to-Set Disjoint Paths Problem in Pancake Graphs" in IEICE TRANSACTIONS on Information,
vol. E86-D, no. 9, pp. 1628-1633, September 2003, doi: .
Abstract: In this paper, we give an algorithm for the node-to-set disjoint paths problem in pancake graphs with its evaluation results. The algorithm is of polynomial order of n for an n-pancake graph. It is based on recursion and divided into two cases according to the distribution of destination nodes in classes into which all the nodes in a pancake graph are categorized. The sum of lengths of paths obtained and the time complexity of the algorithm are estimated and the average performance is evaluated based on computer simulation.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_9_1628/_p
Copy
@ARTICLE{e86-d_9_1628,
author={Keiichi KANEKO, Yasuto SUZUKI, },
journal={IEICE TRANSACTIONS on Information},
title={Node-to-Set Disjoint Paths Problem in Pancake Graphs},
year={2003},
volume={E86-D},
number={9},
pages={1628-1633},
abstract={In this paper, we give an algorithm for the node-to-set disjoint paths problem in pancake graphs with its evaluation results. The algorithm is of polynomial order of n for an n-pancake graph. It is based on recursion and divided into two cases according to the distribution of destination nodes in classes into which all the nodes in a pancake graph are categorized. The sum of lengths of paths obtained and the time complexity of the algorithm are estimated and the average performance is evaluated based on computer simulation.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Node-to-Set Disjoint Paths Problem in Pancake Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 1628
EP - 1633
AU - Keiichi KANEKO
AU - Yasuto SUZUKI
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2003
AB - In this paper, we give an algorithm for the node-to-set disjoint paths problem in pancake graphs with its evaluation results. The algorithm is of polynomial order of n for an n-pancake graph. It is based on recursion and divided into two cases according to the distribution of destination nodes in classes into which all the nodes in a pancake graph are categorized. The sum of lengths of paths obtained and the time complexity of the algorithm are estimated and the average performance is evaluated based on computer simulation.
ER -
English
