Theory and Applications of Satisfiability Testing
From MaRDI portal
Publication:5325861
DOI10.1007/b95238zbMath1204.68109OpenAlexW2494235144WikidataQ56039662 ScholiaQ56039662MaRDI QIDQ5325861
Publication date: 24 July 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/b95238
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (32)
On finding short resolution refutations and small unsatisfiable subsets ⋮ An enumerative algorithm for \#2SAT ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Community Structure Inspired Algorithms for SAT and #SAT ⋮ Constraint satisfaction with bounded treewidth revisited ⋮ Backdoors to Satisfaction ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ Paradigms for parameterized enumeration ⋮ Complexity and approximability of parameterized MAX-CSPs ⋮ Small Resolution Proofs for QBF using Dependency Treewidth ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ SAT backdoors: depth beats size ⋮ Unnamed Item ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Constraint satisfaction with succinctly specified relations ⋮ Backdoors for linear temporal logic ⋮ On efficiently solvable cases of quantum \(k\)-SAT ⋮ Consequence-based and fixed-parameter tractable reasoning in description logics ⋮ Succinct certification of monotone circuits ⋮ Visualizing SAT instances and runs of the DPLL algorithm ⋮ Solving \#SAT using vertex covers ⋮ New width parameters for SAT and \#SAT ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable ⋮ Succinct monotone circuit certification: planarity and parameterized complexity ⋮ Unnamed Item ⋮ A note on width-parameterized SAT: an exact machine-model characterization ⋮ Strong Backdoors for Default Logic ⋮ Using decomposition-parameters for QBF: mind the prefix! ⋮ Computational properties of argument systems satisfying graph-theoretic constraints ⋮ Connecting knowledge compilation classes and width parameters
This page was built for publication: Theory and Applications of Satisfiability Testing
