An algorithm for disjoint paths in bubble‐sort graphs
Yasuto Suzuki, Keiichi Kaneko · Systems and Computers in Japan · 2006
Abstract Ann‐dimensional bubble‐sort graph is regular and symmetric. It hasn! nodes and (n−1)n!/2 edges while its connectivity and diameter aren−1 andn(n−1)/2, respectively. Bubble‐sort graphs are attracting attention because of their simple, symmetric, and recursive structure. In this paper, for ann‐bubble‐sort graph, we give anO(n5)‐time algorithm that solves the node‐to‐set disjoint paths problem: Given a source nodesand a set D = d1, d2, …, dk(s ∉ D) ofkdestination nodes in ak‐connected graphG, findkpaths fromstodi(1≤i≤k) that are node‐disjoint except fors. Once thesekpaths are obtained, they achieve fault tolerance; that is, at least one path can survive withk−1 faulty components. We also show that the total length ofn−1 paths given by the algorithm isO(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 areO(n4.7) andO(n3.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