Average Time Analysis of Clause Order Backtracking

DOI10.1137/0222023MaRDI QIDQ4032940zbMATH OpenOpenAlexFDO

Authors Khaled M. Bugrara, Paul Walton jun. Purdom

Publication date 17 May 1993

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

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

zbMATH Keywords

NP-completesatisfiabilitycombinatorial searchpure literal ruleBacktrackingaverage timeDavis-Putnam

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Recommendations

• Probe Order Backtracking
• scientific article; zbMATH DE number 1113993
• Polynomial-average-time satisfiability problems
• Backtracking and random constraint satisfaction
• Exponential Average Time for the Pure Literal Rule

Cited in

(8)

• scientific article; zbMATH DE number 4080977 (Why is no real title available?)
• scientific article; zbMATH DE number 2188496 (Why is no real title available?)
• A BDD SAT solver for satisfiability testing: An industrial case study
• The \(Multi\)-SAT algorithm
• An artificial neural network satisfiability tester
• A complete adaptive algorithm for propositional satisfiability
• A Variational Method for Analysing Unit Clause Search
• scientific article; zbMATH DE number 4060775 (Why is no real title available?)

This page was built for publication: Average Time Analysis of Clause Order Backtracking

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