For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Node-to-Node Disjoint Paths Problem in Möbius Cubes
David KOCIK Keiichi KANEKO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2017/08/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Dependable Computing
container problem, hypercube, multicomputer, interconnection network, parallel processing, dependable computing, performance evaluation,
Full Text: PDF>>
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.