 Presentation 2004/7/23 Fault-tolerant routing algorithm in bubble-sort graphs Yasuto SUZUKI, Keiichi KANEKO, PDF download Page Link (See Japanese page) An n-dimensional bubble-sort graph is a graph which is regular and symmetric. It has n! nodes and (n - l)n!/2 edges while its connectivity and diameter are n - 1, n(n - l)/2, respectively. Much attention is paid to a bubble-sort graph because of its simple and regular 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 node s and a node set D = (d_1, d_2, ・・・) d_k} in a k-connected graph, find k internally disjoint paths between s and each d_i's in D. Once this problem solved, in the communication between s and d, at least one node can receive the massage even if the topology has k - 1 faulty edges and/or nodes. We also show that the total length of n - 1 paths given by the algorithm is of O(n^3). The simulation results show that the average time complexity of the algorithm and the average total length of the paths given by the algorithm are of O(n^<4.7>) and O(n^3), respectively. (See Japanese page) bubble-sort graph / disjoint paths / multicast / fault tolerance / polynomial-order algorithm DC2004-13

Committee Conference Information DC 2004/7/23(1days) (See Japanese page) (See Japanese page)

Registration To Paper Information Dependable Computing (DC) JPN (See Japanese page) (See Japanese page) Fault-tolerant routing algorithm in bubble-sort graphs bubble-sort graph disjoint paths multicast fault tolerance polynomial-order algorithm Yasuto SUZUKI Faculty of Technology, Tokyo University of Agriculture and Technology() Keiichi KANEKO Faculty of Technology, Tokyo University of Agriculture and Technology 2004/7/23 DC2004-13 vol.104 239 pp.pp.- 6