IEICE TRANSACTIONS on Information
Node-to-Node Disjoint Paths Problem in Möbius Cubes
Summary :
The Möbius cube is a variant of the hypercube. Its advantage is that it can connect the same number of nodes as a hypercube but with almost half the diameter of the hypercube. We propose an algorithm to solve the node-to-node disjoint paths problem in n-Möbius cubes in polynomial-order time of n. We provide a proof of correctness of the algorithm and estimate that the time complexity is O(n2) and the maximum path length is 3n-5.
- Publication
- IEICE TRANSACTIONS on Information Vol.E100-D No.8 pp.1837-1843
- Publication Date
- 2017/08/01
- Publicized
- 2017/04/25
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2016EDP7475
- Type of Manuscript
- PAPER
- Category
- Dependable Computing
Authors
David KOCIK
Czech Technical University in Prague
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, Keiichi KANEKO, "Node-to-Node Disjoint Paths Problem in Möbius Cubes" in IEICE TRANSACTIONS on Information,
vol. E100-D, no. 8, pp. 1837-1843, August 2017, doi: 10.1587/transinf.2016EDP7475.
Abstract: The Möbius cube is a variant of the hypercube. Its advantage is that it can connect the same number of nodes as a hypercube but with almost half the diameter of the hypercube. We propose an algorithm to solve the node-to-node disjoint paths problem in n-Möbius cubes in polynomial-order time of n. We provide a proof of correctness of the algorithm and estimate that the time complexity is O(n2) and the maximum path length is 3n-5.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2016EDP7475/_p
Copy
@ARTICLE{e100-d_8_1837,
author={David KOCIK, Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={Node-to-Node Disjoint Paths Problem in Möbius Cubes},
year={2017},
volume={E100-D},
number={8},
pages={1837-1843},
abstract={The Möbius cube is a variant of the hypercube. Its advantage is that it can connect the same number of nodes as a hypercube but with almost half the diameter of the hypercube. We propose an algorithm to solve the node-to-node disjoint paths problem in n-Möbius cubes in polynomial-order time of n. We provide a proof of correctness of the algorithm and estimate that the time complexity is O(n2) and the maximum path length is 3n-5.},
keywords={},
doi={10.1587/transinf.2016EDP7475},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - Node-to-Node Disjoint Paths Problem in Möbius Cubes
T2 - IEICE TRANSACTIONS on Information
SP - 1837
EP - 1843
AU - David KOCIK
AU - Keiichi KANEKO
PY - 2017
DO - 10.1587/transinf.2016EDP7475
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2017
AB - The Möbius cube is a variant of the hypercube. Its advantage is that it can connect the same number of nodes as a hypercube but with almost half the diameter of the hypercube. We propose an algorithm to solve the node-to-node disjoint paths problem in n-Möbius cubes in polynomial-order time of n. We provide a proof of correctness of the algorithm and estimate that the time complexity is O(n2) and the maximum path length is 3n-5.
ER -
English
