The Container Problem in Bubble-Sort Graphs

スポンサーリンク

概要

• 論文の詳細を見る

• Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.

• （社）電子情報通信学会の論文
• 2008-04-01

著者

• Kaneko Keiichi

  Graduate School Of Engineering Tokyo University Of Agriculture And Technology

• SUZUKI Yasuto

  Graduate School of Engineering, Tokyo University of Agriculture and Technology

• Suzuki Yasuto

  Graduate School Of Engineering Tokyo University Of Agriculture And Technology

関連論文

• Hamiltonian Cycles and Hamiltonian Paths in Faulty Burnt Pancake Graphs(Algorithm Theory)
• The Container Problem in Bubble-Sort Graphs
• An Algorithm for Node-to-Node Disjoint Paths Problem in Burnt Pancake Graphs(Dependable Computing)

スポンサーリンク