TY - CHAP
T1 - Fast deterministic backtrack search
AU - Herley, Kieian T.
AU - Pietiacaprina, Andtea
AU - Pucci, Geppino
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1996
Y1 - 1996
N2 - The backtrack search problem involves visiting all the nodes of an arbitrary binary tree given a pointer to its root, subject to the constraint that the children of a node are revealed only after their parent is visited. This note describes a fast, deterministic backtrack search algorithm for a p-processor COMMON CRCW-PRAM that visits any n-node tree of height h in time O((n/р + h)(log log log p)2). This up-perbound compares favorably with a natural Ω(n/ρ + h) lower bound for this problem. Our approach embodies novel, efficient techniques for dynamically assigning tree-nodes to processors to ensure that the work is shared equitably among them.
AB - The backtrack search problem involves visiting all the nodes of an arbitrary binary tree given a pointer to its root, subject to the constraint that the children of a node are revealed only after their parent is visited. This note describes a fast, deterministic backtrack search algorithm for a p-processor COMMON CRCW-PRAM that visits any n-node tree of height h in time O((n/р + h)(log log log p)2). This up-perbound compares favorably with a natural Ω(n/ρ + h) lower bound for this problem. Our approach embodies novel, efficient techniques for dynamically assigning tree-nodes to processors to ensure that the work is shared equitably among them.
UR - https://www.scopus.com/pages/publications/84947760442
U2 - 10.1007/3-540-61440-0_162
DO - 10.1007/3-540-61440-0_162
M3 - Chapter
AN - SCOPUS:84947760442
SN - 3540614400
SN - 9783540614401
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 598
EP - 609
BT - Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings
A2 - Meyer auf der Heide, Friedhelm
A2 - Monien, Burkhard
PB - Springer Verlag
T2 - 23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996
Y2 - 8 July 1996 through 12 July 1996
ER -