.png){kind=icon}
返回
An efficient algorithm for the k-pairwise disjoint paths problem in hypercubes
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.2000.1632.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
A graph G(V, E) (/V/ greater than or equal to 2k) satisfies property A(k) if given k pairs of distinct nodes (s(1), t(1)),..., (s(k), t(k)) of V(G), there are k mutually node-disjoint paths, one connecting s(i) and t(i) for each i. 1 less than or equal to i less than or equal to k. A necessary condition for any graph to satisfy A(k) is that it is (2k - 1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension ir (which are n-connected) satisfy A([n/2]). In this paper we give an algorithm which, given k = ([n/2]) pairs of distinct nodes (s(1), t(1)),..., (s(k), t(k)) in the n-dimensional hypercube, finds the k disjoint paths of length at most n + [log n] + 1 in O(n(2) log* n) time. (C) 2000 Academic Press.
Keyword:
disjoint paths
interconnection networks
algorithms
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏
没有更多内容
没有更多内容