Presentation 2004/7/23
Fault-tolerant routing algorithm in bubble-sort graphs
Yasuto SUZUKI, Keiichi KANEKO,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) 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.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) bubble-sort graph / disjoint paths / multicast / fault tolerance / polynomial-order algorithm
Paper # DC2004-13
Date of Issue

Conference Information
Committee DC
Conference Date 2004/7/23(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Vice Chair

Paper Information
Registration To Dependable Computing (DC)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) Fault-tolerant routing algorithm in bubble-sort graphs
Sub Title (in English)
Keyword(1) bubble-sort graph
Keyword(2) disjoint paths
Keyword(3) multicast
Keyword(4) fault tolerance
Keyword(5) polynomial-order algorithm
1st Author's Name Yasuto SUZUKI
1st Author's Affiliation Faculty of Technology, Tokyo University of Agriculture and Technology()
2nd Author's Name Keiichi KANEKO
2nd Author's Affiliation Faculty of Technology, Tokyo University of Agriculture and Technology
Date 2004/7/23
Paper # DC2004-13
Volume (vol) vol.104
Number (no) 239
Page pp.pp.-
#Pages 6
Date of Issue