.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
disjoint paths
interconnection networks
algorithms
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSave
ShareSave no more
no more