An Algorithm for Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs(Dependable Communication)(<Special Issue>Dependable Computing)

スポンサーリンク

概要

• 論文の詳細を見る

• A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm.

• 社団法人電子情報通信学会の論文
• 2003-12-01

著者

• Kaneko Keiichi

  Faculty Of Technology Tokyo University Of Agriculture And Technology

関連論文

• Internally-Disjoint Paths Problem in Bi-Rotator Graphs(Dependable Computing)
• Node-to-Set Disjoint Paths Problem in Pancake Graphs(Special Issue on Parallel and Distributed Computing, Applications and technologies)
• Node-Disjoint Paths Algorithm in a Transposition Graph(Algorithm Theory)
• An Algorithm for Node-Disjoint Paths in Pancake Graphs
• Minimum Feedback Node Sets in Trivalent Cayley Graphs(Special Issue on Parallel and Distributed Computing, Applications and technologies)
• Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks
• An Algorithm for Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs(Dependable Communication)(Dependable Computing)

スポンサーリンク