Set-to-Set Disjoint Path Routing Algorithm in Burnt Pancake Graphs

摘要

As a variation of the pancake graph interconnection network, the burnt pancake graph network has a merit that it can connect many nodes while retaining a low degree. With a degree of n, a burnt pancake graph B_n connects n! x 2~n nodes. This paper proposes an algorithm solving the set-to-set disjoint paths routing problem inside a burnt pancake graph. In a B_n, given a set 5 of n source nodes and a set T of n destination nodes, this algorithm finds n disjoint paths of length at most 2n + 12 between the nodes of S and T in O(n~4) time complexity.