Node-to-Set Disjoint Paths with Optimal Length in Star Graphs (Special Issue on Parallel and Distributed Supercomputing)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we consider the following node-to-set disjoint paths problem: given a node s and a set T={t_1,…, t_k} of k nodes in a k-connected graph G, find k node-disjoint paths s→t_i, 1≦i≦k. We give an O(n^2) time algorithm for the node-to-set disjoint paths problem in n-dimensional star graphs G_n which are (n-1)-connected. The algorithm finds the n-1 node-disjoint Paths of length at most d(G_n)+1 for n ≠ 4,6 and at most d(G_n)+2 for n=4,6, where d(G_n)=⌊(3(n-1))/2⌋ is the diameter of G_n. d(G_n)+1 and d(G_n)+2 are also the lower bounds on the length of the paths for the above problem in G_n for n ≠ 4,6 and n=4,6, respectively.
- 一般社団法人電子情報通信学会の論文
- 1997-04-25
著者
-
Gu Qian-ping
Department Of Computer Software The University Of Aizu
-
Peng Shietung
Department Of Computer Software Distributed Parallel Processing Laboratory The University Of Aizu
関連論文
- A Parallel Algorithm for the Longest Path Problem on Acyclic Graphs with Integer Arc Lengths
- Efficient algorithms for Disjoint Paths in Hypercubes and Star Networks
- Efficient Algorithms for Node Disjoint Path Problems
- Set-To-Set Fault Tolerant Routing in Hypercubes (Special Section on Discrete Mathematics and Its Applications)
- d-Separated Paths in Hypercubes and Star Graphs
- Design of Array Processors for 2-D Discrete Fourier Transform (Special Issue on Parallel and Distributed Supercomputing)
- Distributed Algorithms for Leader Election on Partially Ordered Keys (特集 マルチメディア通信プロトコル)
- Fault Tolerant Routing in Toroidal Networks (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
- Set-To-Set Fault Tolerant Routing in Star Graphs
- Efficient Broadcasting Algorithms in Faulty Hypercubes and Star Graphs
- Node-to-Set Disjoint Paths with Optimal Length in Star Graphs (Special Issue on Parallel and Distributed Supercomputing)
- Linear Time Algorithms for Fault Tolerant Routing in Hypercubes and Star Graphs