Node-to-Set Disjoint Paths Problem in a Möbius Cube
Summary :
This paper proposes an algorithm that solves the node-to-set disjoint paths problem in an n-Möbius cube in polynomial-order time of n. It also gives a proof of correctness of the algorithm as well as estimating the time complexity, O(n4), and the maximum path length, 2n-1. A computer experiment is conducted for n=1,2,...,31 to measure the average performance of the algorithm. The results show that the average time complexity is gradually approaching to O(n3) and that the maximum path lengths cannot be attained easily over the range of n in the experiment.
- Publication
- IEICE TRANSACTIONS on Information Vol.E99-D No.3 pp.708-713
- Publication Date
- 2016/03/01
- Publicized
- 2015/12/14
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2015EDP7331
- Type of Manuscript
- PAPER
- Category
- Dependable Computing
Authors
David KOCIK
Czech Technical University in Prague
Yuki HIRAI
Tokyo University of Agriculture and Technology
Keiichi KANEKO
Tokyo University of Agriculture and Technology
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
David KOCIK, Yuki HIRAI, Keiichi KANEKO, "Node-to-Set Disjoint Paths Problem in a Möbius Cube" in IEICE TRANSACTIONS on Information,
vol. E99-D, no. 3, pp. 708-713, March 2016, doi: 10.1587/transinf.2015EDP7331.
Abstract: This paper proposes an algorithm that solves the node-to-set disjoint paths problem in an n-Möbius cube in polynomial-order time of n. It also gives a proof of correctness of the algorithm as well as estimating the time complexity, O(n4), and the maximum path length, 2n-1. A computer experiment is conducted for n=1,2,...,31 to measure the average performance of the algorithm. The results show that the average time complexity is gradually approaching to O(n3) and that the maximum path lengths cannot be attained easily over the range of n in the experiment.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2015EDP7331/_p
Copy
@ARTICLE{e99-d_3_708,
author={David KOCIK, Yuki HIRAI, Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={Node-to-Set Disjoint Paths Problem in a Möbius Cube},
year={2016},
volume={E99-D},
number={3},
pages={708-713},
abstract={This paper proposes an algorithm that solves the node-to-set disjoint paths problem in an n-Möbius cube in polynomial-order time of n. It also gives a proof of correctness of the algorithm as well as estimating the time complexity, O(n4), and the maximum path length, 2n-1. A computer experiment is conducted for n=1,2,...,31 to measure the average performance of the algorithm. The results show that the average time complexity is gradually approaching to O(n3) and that the maximum path lengths cannot be attained easily over the range of n in the experiment.},
keywords={},
doi={10.1587/transinf.2015EDP7331},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Node-to-Set Disjoint Paths Problem in a Möbius Cube
T2 - IEICE TRANSACTIONS on Information
SP - 708
EP - 713
AU - David KOCIK
AU - Yuki HIRAI
AU - Keiichi KANEKO
PY - 2016
DO - 10.1587/transinf.2015EDP7331
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E99-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2016
AB - This paper proposes an algorithm that solves the node-to-set disjoint paths problem in an n-Möbius cube in polynomial-order time of n. It also gives a proof of correctness of the algorithm as well as estimating the time complexity, O(n4), and the maximum path length, 2n-1. A computer experiment is conducted for n=1,2,...,31 to measure the average performance of the algorithm. The results show that the average time complexity is gradually approaching to O(n3) and that the maximum path lengths cannot be attained easily over the range of n in the experiment.
ER -
English
