Parameterized and subexponential-time complexity of satisfiability problems and applications
DOI10.1016/J.TCS.2015.08.029zbMATH Open1332.68082OpenAlexW2158951688MaRDI QIDQ896108FDOQ896108
Authors: Iyad 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
Recommendations
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Parameterized complexity of weighted satisfiability problems
- Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
- Parameterized complexity and subexponential-time computability
- Tight lower bounds for certain parameterized NP-hard problems
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
- Introduction to algorithms
- Fundamentals of parameterized complexity
- Optimization, approximation, and complexity classes
- Which problems have strongly exponential complexity?
- Parametrized complexity theory.
- Title not available (Why is that?)
- On the possibility of faster \textsc{SAT} algorithms
- On the complexity of \(k\)-SAT
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- On the existence of subexponential parameterized algorithms
- Strong computational lower bounds via parameterized complexity
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- Vertex cover: Further observations and further improvements
- Tight lower bounds for certain parameterized NP-hard problems
- Incremental list coloring of graphs, parameterized by conservation
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- An improved deterministic local search algorithm for 3-SAT
- Title not available (Why is that?)
- On miniaturized problems in parameterized complexity theory
- Parameterized complexity and subexponential-time computability
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
- STACS 2004
- On parameterized exponential time complexity
- Algorithms for Variable-Weighted 2-SAT and Dual Problems
Cited In (12)
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Polynomial-average-time satisfiability problems
- Solving QSAT in sublinear depth
- A perspective on certain polynomial-time solvable classes of satisfiability
- Tight lower bounds for certain parameterized NP-hard problems
- Solving the resolution-free SAT problem by submodel propagation in linear time
- On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances
- Mathematical Foundations of Computer Science 2005
- On the existence of subexponential parameterized algorithms
- Parameterized complexity and subexponential-time computability
- On O(Tlog T) reduction from RAM computations to satisfiability
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
This page was built for publication: Parameterized and subexponential-time complexity of satisfiability problems and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896108)
