A note on width-parameterized SAT: an exact machine-model characterization
From MaRDI portal
Publication:990090
DOI10.1016/j.ipl.2009.09.012zbMath1206.68150OpenAlexW1981679584MaRDI QIDQ990090
Publication date: 2 September 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.09.012
computational complexitycompletenesspathwidthSATfixed parameter space tractabilitymachine characterization
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Cites Work
- Unnamed Item
- Unnamed Item
- Which problems have strongly exponential complexity?
- Parametrized complexity theory.
- Complexity and Algorithms for Well-Structured k-SAT Instances
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Theory and Applications of Satisfiability Testing
This page was built for publication: A note on width-parameterized SAT: an exact machine-model characterization