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

Keiichi KANEKO
Yasuto SUZUKI

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E84-D    No.9    pp.1155-1163
Publication Date: 2001/09/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithms
Keyword: 
rotator graphs,  node-to-set disjoint paths problem,  interconnection network,  parallel and distributed processing,  

Full Text: PDF>>
Buy this Article



Summary: 
In this paper, we give an algorithm for the node-to-set disjoint paths problem in rotator graphs with its evaluation results. The algorithm is based on recursion and it is divided into cases according to the distribution of destination nodes in classes into which all the nodes in a rotator graph are categorized. The sum of the length of paths obtained and the time complexity of the algorithm are estimated and verified by computer simulation.