An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

✍ Scribed by Qian-Ping Gu; Shietung Peng

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 140 KB
• Volume: 60
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2000.1632

✦ Synopsis

A graph G(V, E) (|V| 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 i 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 n (which are n-connected) satisfy A WnÂ2X . In this paper we give an algorithm which, given k=WnÂ2X 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+Wlog nX+1 in O(n 2 log* n) time.