An Average Time Analysis of Backtracking

DOI10.1137/0210043MaRDI QIDQ3911407zbMATH OpenOpenAlexFDO

Authors Cynthia A. Brown, Paul Walton jun. Purdom

Publication date 1981

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

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

zbMATH Keywords

analysis of algorithmsNP- completenesssearchingsolutions of a random predicate

Mathematics Subject Classification ID

Theory of software (68N99) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Cited in

(13)

• Polynomial-average-time satisfiability problems
• Revisiting global constraint satisfaction
• Backtracking with multi-level dynamic search rearrangement
• Integer programs for logic constraint satisfaction
• Exact satisfiability, a natural extension of set partition, and its average case behavior
• The expected complexity of analytic tableaux analyses in propositional calculus. II
• A BDD SAT solver for satisfiability testing: An industrial case study
• Average running time analysis of an algorithm to calculate the size of the union of Cartesian products.
• On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
• The Multi-SAT algorithm
• scientific article; zbMATH DE number 1334602 (Why is no real title available?)
• Average time analyses of simplified Davis-Putnam procedures
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem

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

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