
For FullText 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.

InternallyDisjoint Paths Problem in BiRotator Graphs
Keiichi KANEKO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E88D
No.7
pp.16781684 Publication Date: 2005/07/01
Online ISSN:
DOI: 10.1093/ietisy/e88d.7.1678
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Dependable Computing Keyword: container problem, internallydisjoint paths, birotator 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 birotator graph is obtained by making each edge of a rotator graph bidirectional. In a birotator 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 birotator 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 nbirotator 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(n^{3}) and 4n5, respectively. Average performance of the algorithm is also evaluated by computer experiments.

