Probe Order Backtracking

DOI10.1137/S0097539793256053MaRDI QIDQ4337643zbMATH OpenOpenAlexFDO

Authors G. Neil Haven, Paul Walton jun. Purdom

Publication date 26 May 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539793256053

zbMATH Keywords

Algorithm for constraint-satisfaction problemsaverage timebacktrackingcombinatorial searchNP-completesatisfiabilitysearching

Mathematics Subject Classification ID

Classical propositional logic (03B05) Asymptotic enumeration (05A16) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 1113993
• Average Time Analysis of Clause Order Backtracking
• Backtracking and random constraint satisfaction
• Polynomial-average-time satisfiability problems

Cited in

(5)

• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• Average Time Analysis of Clause Order Backtracking
• scientific article; zbMATH DE number 1113993 (Why is no real title available?)
• scientific article; zbMATH DE number 2188496 (Why is no real title available?)
• Results related to threshold phenomena research in satisfiability: Lower bounds

This page was built for publication: Probe Order Backtracking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4337643)