Presentation 2003/7/30
Node-to-Node Internally Disjoint Paths Problem in Bubble-Sort Graphs
Keiichi KANEKO, Yasuto SUZUKI,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) A bubble-sort graph is a variant of Cayley graphs and it is suitable as a toplogy for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on nth bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between arbitrary two nodes in polynomial order of n which is the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of path lengths after proving the correctness of the algorithm. Moreover, we report the results of computer experiment to evaluate average performance of the algorithm.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Bubble-Sort Graphs / Internaly Disjoint Paths / Polynomial Algorithm / Fault Tolerance
Paper # DC2003-12
Date of Issue

Conference Information
Committee DC
Conference Date 2003/7/30(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

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) Node-to-Node Internally Disjoint Paths Problem in Bubble-Sort Graphs
Sub Title (in English)
Keyword(1) Bubble-Sort Graphs
Keyword(2) Internaly Disjoint Paths
Keyword(3) Polynomial Algorithm
Keyword(4) Fault Tolerance
1st Author's Name Keiichi KANEKO
1st Author's Affiliation Faculty of Technology, Tokyo University of Agriculture and Technology()
2nd Author's Name Yasuto SUZUKI
2nd Author's Affiliation Faculty of Technology, Tokyo University of Agriculture and Technology
Date 2003/7/30
Paper # DC2003-12
Volume (vol) vol.103
Number (no) 250
Page pp.pp.-
#Pages 6
Date of Issue