Average Time Analysis of Clause Order Backtracking

DOI10.1137/0222023zbMATH Open0770.68066OpenAlexW2038987765MaRDI QIDQ4032940FDOQ4032940

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

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

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)

Cited In (8)

• Title not available (Why is that?)
• Title not available (Why is that?)
• An artificial neural network satisfiability tester
• The \(Multi\)-SAT algorithm
• A complete adaptive algorithm for propositional satisfiability
• A Variational Method for Analysing Unit Clause Search
• Title not available (Why is that?)
• A BDD SAT solver for satisfiability testing: An industrial case study

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)