Node-to-Node Disjoint Paths Problem in Möbius Cubes

David KOCIK  Keiichi KANEKO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.8   pp.1837-1843
Publication Date: 2017/08/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016EDP7475
Type of Manuscript: PAPER
Category: Dependable Computing
Keyword: 
container problem,  hypercube,  multicomputer,  interconnection network,  parallel processing,  dependable computing,  performance evaluation,  

Full Text: PDF>>
Buy this Article




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.