An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes |
| |
| Affiliation: | 1. Department of Computer Science & IT, Guru Ghasidas Vishwavidyalaya, Bilaspur, India;2. Centre for Artificial Intelligence, University of Technology Sydney, Sydney, Australia;3. School of Computational and Integrative Sciences, Jawaharlal Nehru University, New Delhi, India;4. Department of Computer Science and Engineering, Indian Institute of Technology Indore, India;5. School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore;6. School of Computer and Technology, Nantong University, Nantong, China;1. Education and Counseling Center of Mental Health, Ocean University of China, Qingdao 266100, China;2. Faculty of Psychology, Beijing Normal University, Beijing 100875, China;4. School of Psychology, Nanjing Normal University, Nanjing 210003, China;1. Institute of Child and Adolescent Health, School of Public Health, Peking University, Beijing, China;2. The National Clinical Research Center for Mental Disorders & Beijing Key Laboratory of Mental Disorders, Beijing Anding Hospital & the Advanced Innovation Center for Human Brain Protection, Capital Medical University, Beijing, China;3. Mental Health and Behavioral Science Service, Bruce W. Carter VA Medical Center, Miami, FL, United States;4. Beijing Institute of Mental Health, Beijing, China |
| |
| Abstract: | A graph G(V, E) (|V|?2k) satisfies property Ak if, given k pairs of distinct nodes (s1, t1), …, (sk, tk) of V(G), there are k mutually node-disjoint paths, one connecting si and ti for each i, 1?i?k. A necessary condition for any graph to satisfy Ak 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?n/2?. In this paper we give an algorithm which, given k=?n/2? pairs of distinct nodes (s1, t1), …, (sk, tk) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+?log n?+1 in O(n2 log* n) time. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
