Parameterized and subexponential-time complexity of satisfiability problems and applications

DOI10.1016/j.tcs.2015.08.029zbMath1332.68082OpenAlexW2158951688MaRDI QIDQ896108

Iyad A. Kanj, Stefan Szeider

Publication date: 11 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.08.029

zbMATH Keywords

parameterized complexitycircuit satisfiabilitysubexponential-time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
• An improved deterministic local search algorithm for 3-SAT
• On miniaturized problems in parameterized complexity theory
• Strong computational lower bounds via parameterized complexity
• On parameterized exponential time complexity
• Optimization, approximation, and complexity classes
• Which problems have strongly exponential complexity?
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• On the existence of subexponential parameterized algorithms
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• Vertex Cover: Further Observations and Further Improvements
• Parameterized Complexity and Subexponential-Time Computability
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• An Isomorphism Between Subexponential and Parameterized Complexity Theory
• Incremental List Coloring of Graphs, Parameterized by Conservation
• Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
• Algorithms for Variable-Weighted 2-SAT and Dual Problems
• STACS 2004
• On the complexity of \(k\)-SAT

This page was built for publication: Parameterized and subexponential-time complexity of satisfiability problems and applications