An Algorithm for Node-to-Set Disjoint Paths Problem in Bi-Rotator Graphs(Parallel/Distributed Algorithms, <Special Section> Parallel/Distributed Computing and Networking)

スポンサーリンク

概要

• 論文の詳細を見る

• An algorithm is described for solving the node-to-set disjoint paths problem in bi-rotator graphs, which are obtained by making each edge of a rotator graph bi-directional. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into three cases according to the distribution of destination nodes in the classes into which the nodes in a bi-rotator graph are categorized. We estimated that it obtains 2n-3 disjoint paths with a time complexity of O(n^5), that the sum of the path lengths is O(n^3), and that the length of the maximum path is O(n^2). Computer experiment showed that the average execution time was O(n^<3.9>) and, the average sum of the path lengths was O(n^<3.0>).

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

著者

• Kaneko Keiichi

  The Faculty Of Engineering Tokyo University Of Agriculture And Technology

• Kaneko Keiichi

  The Faculty Of Engineering Chiba University

関連論文

• Dynamic Constructive Fault Tolerant Algorithm for Feedforward Neural Networks
• An Algorithm for Node-to-Set Disjoint Paths Problem in Bi-Rotator Graphs(Parallel/Distributed Algorithms, Parallel/Distributed Computing and Networking)

スポンサーリンク