An Algorithm for Node-to-Set Disjoint Paths Problem in Bi-Rotator Graphs

Keiichi KANEKO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.2   pp.647-653
Publication Date: 2006/02/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.2.647
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Parallel/Distributed Computing and Networking)
Category: Parallel/Distributed Algorithms
Keyword: 
node-to-set disjoint paths problem,  bi-rotator graphs,  fault tolerance,  parallel computation,  routing algorithm,  

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


Summary: 
An algorithm is described for solving the node-to-set disjoint paths problem in bi-rotator graphs, which are obtained by making each edge of a rotator graph bi-directional. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into three cases according to the distribution of destination nodes in the classes into which the nodes in a bi-rotator graph are categorized. We estimated that it obtains 2n-3 disjoint paths with a time complexity of O(n5), that the sum of the path lengths is O(n3), and that the length of the maximum path is O(n2). Computer experiment showed that the average execution time was O(n3.9) and, the average sum of the path lengths was O(n3.0).