An Algorithm for k-Pairwise Cluster-Fault-Tolerant Disjoint Paths in a Burnt Pancake Graph

摘要

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(kn) and the maximum path length is 2n + 15.