Node-Disjoint Paths Algorithm in a Transposition Graph(Algorithm Theory)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we give an algorithm for the node-to-set disjoint paths problem in a transposition graph. The algorithm is of polynomial order of n for an n-transposition graph. It is based on recursion and divided into two cases according to the distribution of destination nodes. The maximum length of each path and the time complexity of the algorithm are estimated theoretically to be O(n^7) and 3n-5, respectively, and the average performance is evaluated based on computer experiments.
- 社団法人電子情報通信学会の論文
- 2006-10-01
著者
-
Kaneko Keiichi
Faculty Of Technology Tokyo University Of Agriculture And Technology
-
SUZUKI Yasuto
Fujitsu Access Limited
-
NAKAMORI Mario
Faculty of Technology, Tokyo University of Agriculture and Technology
-
Nakamori Mario
Faculty Of Technology Tokyo University Of Agriculture And Technology
-
Suzuki Yasuto
Tokyo Univ. Agriculture And Technol. Koganei‐shi Jpn
関連論文
- 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)