.png){kind=icon}
.png){kind=icon}
Return
Space-efficient parallel algorithms for combinatorial search problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.jpdc.2014.09.007.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present space-efficient parallel strategies for two fundamental combinatorial search problems, namely, backtrack search and branch-and-bound, both involving the visit of an n-node tree of height h under the assumption that a node can be accessed only through its father or its children. For both problems we propose efficient algorithms that run on a p-processor distributed-memory machine. For backtrack search, we give a deterministic algorithm running in 0 (n/p + h logp) time, and a Las Vegas algorithm requiring optimal 0 (n/p + h) time, with high probability. Building on the backtrack search algorithm, we also derive a Las Vegas algorithm for branch-and-bound which runs in 0 ((n/p + h logp log n)h log(2) n) time, with high probability. A remarkable feature of our algorithms is the use of only constant space per processor, which constitutes a significant improvement upon previous algorithms whose space requirements per processor depend on the (possibly huge) tree to be explored. (C) 2014 Elsevier Inc. All rights reserved.
Keywords:
Combinatorial search problems
Distributed algorithms
Backtrack search
Branch-and-bound
Space-efficient algorithms
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K