An Analysis of Backtracking with Search Rearrangement

DOI10.1137/0212049zbMath0524.68019OpenAlexW1980584633MaRDI QIDQ3036695

Cynthia A. Brown, Paul Walton jun. Purdom

Publication date: 1983

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

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

zbMATH Keywords

analysis of algorithmsNP-completesearch algorithmsbacktrackingaverage time analysis

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Algorithms in computer science (68W99)

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, An average case analysis of a resolution principle algorithm in mechanical theorem proving., Generating random instances of weighted model counting. An empirical analysis with varying primal treewidth, Average running time analysis of an algorithm to calculate the size of the union of Cartesian products., Solving the satisfiability problem by using randomized approach, Integer programs for logic constraint satisfaction, Average time analyses of simplified Davis-Putnam procedures