An algorithm for the node-to-set disjoint paths problem in burnt pancake graphs

摘要

A burnt pancake graph is a variant of Cayley graphs and it is suitable as a toplogy for massively parallel systems because its degree and diameter are smaller than a hypercube which has similar number of nodes. However, in a burnt pancake graph, its precise diameter or an algorithm to obtain shortest paths in polynomial time of the degree are still unknown like pancake graphs. So, there is much room for further researches. 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 of n which is the degree of the graph. In the algorithm, a notion of a class is introduced and all nodes are classified into classes. Next, the algorithm takes advantage of the recursive structure of a burnt pancake graph, and reduces the generation of paths to n-1 destination nodes to the subproblem in the burnt pancake subgraph to which the source node belongs. The path to the remaining one destination node which is disjoint to other paths is obtained by using a path whose nodes belong to a specific class. In addition, we estimate the time complexity of the algorithm and the sum of path lengths after proving the correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate average performance of the algorithm.