scientific article; zbMATH DE number 7205210

DOI10.4230/LIPIcs.IPEC.2017.26zbMath1443.68073MaRDI QIDQ5111886

Valia Mitsou, Michael Lampis

Publication date: 27 May 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

treewidthexponential time hypothesisquantified SAT

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Related Items (7)

Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Solving projected model counting by utilizing treewidth and its limits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Default logic and bounded treewidth ⋮ Using decomposition-parameters for QBF: mind the prefix!

Cites Work

• Model counting for CNF formulas of bounded modular treewidth
• Satisfiability of acyclic and almost acyclic CNF formulas
• Constraint satisfaction with bounded treewidth revisited
• The polynomial-time hierarchy
• Which problems have strongly exponential complexity?
• Algorithmic meta-theorems for restrictions of treewidth
• The complexity of first-order and monadic second-order logic revisited
• Algorithms for propositional model counting
• Using decomposition-parameters for QBF: mind the prefix!
• Parameterized complexity classes beyond para-NP
• Bounded-width QBF is PSPACE-complete
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• When Trees Grow Low: Shrubs and Fast MSO1
• Fixed-Parameter Tractable Reductions to SAT
• Solving #SAT and MAXSAT by Dynamic Programming
• Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth
• Model Checking Lower Bounds for Simple Graphs
• Complexity and Approximability of Parameterized MAX-CSPs
• Parameterized Algorithms
• Principles and Practice of Constraint Programming – CP 2004
• On the complexity of \(k\)-SAT

This page was built for publication: