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

Keiichi KANEKO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.12   pp.2588-2594
Publication Date: 2003/12/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Dependable Computing)
Category: Dependable Communication
Keyword: 
burnt pancake graph,  disjoint paths,  polynomial algorithm,  fault tolerance,  routing algorithm,  

Full Text: PDF>>
Buy this Article




Summary: 
A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm.