DocumentCode :
3756641
Title :
An Algorithm for k-Pairwise Cluster-Fault-Tolerant Disjoint Paths in a Burnt Pancake Graph
Author :
Masato Tokuda;Yuki Hirai;Keiichi Kaneko
Author_Institution :
Grad. Sch. of Eng., Tokyo Univ. of Agric. &
fYear :
2015
Firstpage :
651
Lastpage :
655
Abstract :
In this paper, we focus on the pairwise cluster-fault-tolerant disjoint path routing problem in a burnt pancake graph, and propose an algorithm that solves the problem in a polynomial time of the degree of the graph. That is, in an n-burnt pancake graph with n -- 2k+1 faulty cluster whose diameters are at most 3, the algorithm can construct fault-free disjoint paths between k pairs of nodes. The time complexity of the algorithm is O(kn3) and the maximum path length is 2n + 15.
Keywords :
"Routing","Clustering algorithms","Time complexity","Computers","Fault tolerance","Fault tolerant systems","Program processors"
Publisher :
ieee
Conference_Titel :
Computational Science and Computational Intelligence (CSCI), 2015 International Conference on
Type :
conf
DOI :
10.1109/CSCI.2015.117
Filename :
7424172
Link To Document :
بازگشت