An Analysis of Backtracking with Search Rearrangement

DOI10.1137/0212049MaRDI QIDQ3036695zbMATH OpenOpenAlexFDO

Authors 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 algorithmsaverage time analysisbacktrackingNP-completesearch algorithms

Mathematics Subject Classification ID

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

Cited in

(9)

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

This page was built for publication: An Analysis of Backtracking with Search Rearrangement

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