Node-to-set disjoint paths in substring reversal graphs

摘要

An n-substring reversal graph Sn is promising as a generic graph because it includes a hypercube, a pancake graph, and a bubble sort graph as its sub graphs. This paper proposes an algorithm N2S that solves the node-to-set disjoint paths problem in substring reversal graphs in polynomial-order time of n. In addition, we prove correctness of the algorithm and estimate the time complexity of the algorithm and the maximum length 6 of paths generated by the algorithm to be O(n6) and 2n−4, respectively.