An Average Time Analysis of Backtracking

DOI10.1137/0210043zbMath0461.68063OpenAlexW2055978814MaRDI QIDQ3911407

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 algorithmssearchingNP- completenesssolutions of a random predicate

Mathematics Subject Classification ID

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

Related Items

Polynomial-average-time satisfiability problems, 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, Revisiting global constraint satisfaction, Backtracking with multi-level dynamic search rearrangement, 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., Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem, The \(Multi\)-SAT algorithm, Integer programs for logic constraint satisfaction, Unnamed Item, Average time analyses of simplified Davis-Putnam procedures