An Algorithm for Node-to-Node Disjoint Paths Problem in Burnt Pancake Graphs(Dependable Computing)

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-burnt pancake graphs in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n^3) and the maximum path length 3n+4. We conducted a computer experiment for n=2 to 100 to measure the average performance of our algorithm. The results show that the average time complexity is O(n^<3.0>) and the maximum path length is 3n+4.

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

著者

• Kaneko Keiichi

  Graduate School Of Engineering Tokyo University Of Agriculture And Technology

• Sawada Naoki

  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)

スポンサーリンク