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

NP-completesatisfiabilitybacktrackingcombinatorial searchsearchingaverage timeAlgorithm for constraint-satisfaction problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Asymptotic enumeration (05A16) 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

(4)

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

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)