Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
From MaRDI portal
Publication:2942439
DOI10.1007/978-3-319-12691-3_48zbMath1332.68081OpenAlexW2173621488MaRDI QIDQ2942439
Publication date: 11 September 2015
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-12691-3_48
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
- 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
- Parameterized Complexity and Subexponential-Time Computability
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
- On Problems as Hard as CNF-SAT
- On the complexity of \(k\)-SAT
