TY - JOUR
T1 - Space-efficient parallel algorithms for combinatorial search problems
AU - Pietrcaprina, Andrea
AU - Pucci, Geppino
AU - Silvestri, Francesco
AU - Vandin, Fabio
PY - 2015/2
Y1 - 2015/2
N2 - 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 O(n/p+hlogp) time, and a Las Vegas algorithm requiring optimal O(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 O((n/p+hlogplogn)hlog2n) 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.
AB - 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 O(n/p+hlogp) time, and a Las Vegas algorithm requiring optimal O(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 O((n/p+hlogplogn)hlog2n) 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.
KW - Combinatorial search problems
KW - Distributed algorithms
KW - Backtrack search
KW - Branch-and-bound
KW - Space-efficient algorithms
KW - Combinatorial search problems
KW - Distributed algorithms
KW - Backtrack search
KW - Branch-and-bound
KW - Space-efficient algorithms
U2 - 10.1016/j.jpdc.2014.09.007
DO - 10.1016/j.jpdc.2014.09.007
M3 - Journal article
SN - 0743-7315
VL - 76
SP - 58
EP - 65
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - February
ER -