1994 International Conference on Parallel Processing-Vol 3 (ICPP'94) A Backjumping Search Algorithm for a Distributed Memory Multicomputer North Carolina State University August 15-August 19 ISBN: 0-8493-2493-9
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICPP.1994.13
Solving Constraint Satisfaction Problems (CSPs) has been subject to intense study by earlier researchers because CSPs can be used to model a whole variety of practical real world problems. This work involves investigation of the performance of parallel backtracking algorithms for solving CSPs. Two classes of backtracking search algorithms are considered: i) chronological backtracking, and ii) dependency directed backtracking, called backjumping. Results show that the new parallel backjumping algorithm retains the efficiency that the sequential algorithm exhibits, while realizing twice the speedup of parallel backtracking for random constraint networks.
Index Terms:
Backjumping, Backtracking, Multi-computer, Parallel Algorithm.
Citation:
James M. Conrad, Jerry Mathew, "A Backjumping Search Algorithm for a Distributed Memory Multicomputer," icpp, vol. 3, pp.243-246, 1994 International Conference on Parallel Processing-Vol 3 (ICPP'94), 1994 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb