Abstract
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(n^5^)โtime algorithm that solves the nodeโtoโset disjoint paths problem: Given a source node s and a set D = d~1~, d~2~, โฆ, d~k~ (s โ D) of k destination nodes in a kโconnected graph G, find k paths from s to d~i~(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(n^3^). 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(n^4.7^) and O(n^3.0^), respectively. ยฉ 2006 Wiley Periodicals, Inc. Syst Comp Jpn, 37(12): 27โ32, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20518