Node-to-set disjoint paths in substring reversal graphs
Sinyu Jung, Keiichi Kaneko · 2011
An n-substring reversal graph Snis 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.