An algorithm for disjoint paths in bubble-sort graphs

An n-dimensional bubble-sort graph is regular and symmetric. It has n! nodes and (n - 1)n!/2 edges while its connectivity and diameter are n - 1 and n(n - 1)/2, respectively. Bubble-sort graphs are attracting attention because of their simple, symmetric, and recursive structure. In this paper, for an n-bubble-sort graph, we give an O(n5)-time algorithm that solves the node-to-set disjoint paths problem: Given a source node s and a set D = {d 1, d2,..., dk] (s ∉ D) of k destination nodes in a k-connected graph G, find k paths from s to di, (1 ≤ i ≤ k) that are node-disjoint except for s. Once these k paths are obtained, they achieve fault tolerance; that is, at least one path can survive with k -1 faulty components. We also show that the total length of n - 1 paths given by the algorithm is O(n3). Computer experiment results show that the average time complexity of the algorithm and the average total length of the paths given by the algorithm are O(n4.7) and O(n3.0), respectively. © 2006 Wiley Periodicals, Inc.