The Container Problem in Bubble-Sort Graphs
Summary :
Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.
- Publication
- IEICE TRANSACTIONS on Information Vol.E91-D No.4 pp.1003-1009
- Publication Date
- 2008/04/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e91-d.4.1003
- Type of Manuscript
- PAPER
- Category
- Algorithm Theory
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
Yasuto SUZUKI, Keiichi KANEKO, "The Container Problem in Bubble-Sort Graphs" in IEICE TRANSACTIONS on Information,
vol. E91-D, no. 4, pp. 1003-1009, April 2008, doi: 10.1093/ietisy/e91-d.4.1003.
Abstract: Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.4.1003/_p
Copy
@ARTICLE{e91-d_4_1003,
author={Yasuto SUZUKI, Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={The Container Problem in Bubble-Sort Graphs},
year={2008},
volume={E91-D},
number={4},
pages={1003-1009},
abstract={Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.},
keywords={},
doi={10.1093/ietisy/e91-d.4.1003},
ISSN={1745-1361},
month={April},}
Copy
TY - JOUR
TI - The Container Problem in Bubble-Sort Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 1003
EP - 1009
AU - Yasuto SUZUKI
AU - Keiichi KANEKO
PY - 2008
DO - 10.1093/ietisy/e91-d.4.1003
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2008
AB - Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.
ER -
English
