On the power of top-down branching heuristics (2008)
AUTHORS:
Järvisalo Matti
,
Junttila Tommi
BOOKTITLE:
Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI-08)
PAGES:
304--309
URL:
http://www.tcs.tkk.fi/~mjj/publications.shtml
@inproceedings{ JarvisaloJ:AAAI08, editor = "Fox, Dieter and Gomes, Carla P.", author = {J{\"a}rvisalo, Matti and Junttila, Tommi}, publisher = "AAAI Press", title = "On the power of top-down branching heuristics", url = "http://www.tcs.tkk.fi/~mjj/publications.shtml", booktitle = "Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI-08)", abstract = "We study the relative best-case performance of DPLL-based structure-aware SAT solvers in terms of the power of the underlying proof systems. The systems result from (i) varying the style of branching and (ii) enforcing dynamic restrictions on the decision heuristics. Considering DPLL both with and without clause learning, we present a relative efficiency hierarchy for refinements of DPLL resulting from combinations of decision heuristics (top-down restricted, justification restricted, and unrestricted heuristics) and branching styles (typical DPLL-style and ATPG-style branching). An an example, for DPLL without clause learning, we establish a strict hierarchy, with the ATPG-style, justification restricted branching variant as the weakest system.", flags = "MCM public", year = "2008", pages = "304--309" }