Internally-Disjoint Paths Problem in Bi-Rotator Graphs

Keiichi KANEKO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.7   pp.1678-1684
Publication Date: 2005/07/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.7.1678
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Dependable Computing
Keyword: 
container problem,  internally-disjoint paths,  bi-rotator graphs,  fault tolerance,  parallel computation,  

Full Text: PDF(386.4KB)
>>Buy this Article


Summary: 
A rotator graph was proposed as a topology for interconnection networks of parallel computers, and it is promising because of its small diameter and small degree. However, a rotator graph is a directed graph that sometimes behaves harmfully when it is applied to actual problems. A bi-rotator graph is obtained by making each edge of a rotator graph bi-directional. In a bi-rotator graph, average distance is improved against a rotator graph with the same number of nodes. In this paper, we give an algorithm for the container problem in bi-rotator graphs with its evaluation results. The solution achieves some fault tolerance such as file distribution based information dispersal technique. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into two cases according to the position of the destination node. The time complexity of the algorithm and the maximum length of paths obtained are estimated to be O(n3) and 4n-5, respectively. Average performance of the algorithm is also evaluated by computer experiments.