Efficient Algorithms for Node Disjoint Path Problems

概要

論文の詳細を見る
Node disjoint path problem has attracted much attentions in both mathematical terms and interconnection network studies due to its numerous applications in fault tolerant routing and so on [2,6]. In this paper, algorithms for the following disjoint path problems are considered: 1. Disjoint paths between a pair of distinct nodes s and t; 2. Disjoint paths between a node s and a set of distinct nodes T={t_1,t_2,...,t_k}; 3. Disjoint paths between a set of distinct nodes S={s_1,s_2,...,s_k} and a set of distinct nodes T={t_1,t_2,...,t_k}; and 4. Disjoint paths between mutually distinct node pairs (s_1,t_1), (s_2,t_2),...,(s_k,t_k). Problems 1,2,3, and 4 are called node-to-node, node-to-set, set-to-set, and k-pairwise disjoint path problems, respectively. In node-to-node and node-to-set disjoint path problem, the disjoint paths may have the common end nodes. By Menger's theorem, there are k disjoint paths for node-to-node, node-to-set, and set-to-set disjoint path problems, in a k-connected graph. k-pairwise disjoint path problem is NP-complete in general graphs for k⦥3 and (2k-1) connectivity is a necessary condition for a graph to have k disjoint paths in k-pairwise disjoint path problem. We give a summary on the algorithms for the above routing problems in hypercube and star interconnection networks. Hypercubes and star graphs are interesting interconnection topologies for multiprocessor system. They possess rich recursive structure and symmetry properties as well as many desirable fault tolerance characteristics. In addition, with regard to the important properties of degree and diameter, the star graph is shown to be markedly superior.
社団法人電子情報通信学会の論文
1994-09-26

Efficient Algorithms for Node Disjoint Path Problems

スポンサーリンク

概要

著者

関連論文

スポンサーリンク