Satisfiability of acyclic and almost acyclic CNF formulas
From MaRDI portal
Publication:385062
DOI10.1016/j.tcs.2012.12.039zbMath1291.68182MaRDI QIDQ385062
Daniël Paulusma, Sebastian Ordyniak, Stefan Szeider
Publication date: 29 November 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.12.039
68Q25: Analysis of algorithms and problem complexity
05C65: Hypergraphs
03B05: Classical propositional logic
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Grundy Distinguishes Treewidth from Pathwidth, Unnamed Item, On optimization problems in acyclic hypergraphs, Are hitting formulas hard for resolution?, On the complexity of binary polynomial optimization over acyclic hypergraphs, Tractability in constraint satisfaction problems: a survey, Model counting for CNF formulas of bounded modular treewidth, Backdoors for linear temporal logic, Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT, New width parameters for SAT and \#SAT, Backdoors to planning, Paradigms for parameterized enumeration, Complexity and approximability of parameterized MAX-CSPs, Parameterized Compilation Lower Bounds for Restricted CNF-Formulas, Strong Backdoors for Default Logic, On Compiling CNFs into Structured Deterministic DNNFs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On finding solutions for extended Horn formulas
- Hypertree decompositions and tractable queries
- Chordal deletion is fixed-parameter tractable
- A partial k-arboretum of graphs with bounded treewidth
- Efficient graph representations
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Upper bounds to the clique width of graphs
- Algorithms for propositional model counting
- Solving \#SAT using vertex covers
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Parametrized complexity theory.
- Approximating clique-width and branch-width
- Degrees of acyclicity for hypergraphs and relational database schemes
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Graph Classes: A Survey
- Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
- A Computing Procedure for Quantification Theory
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
