Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345MaRDI QIDQ5492890zbMATH OpenOpenAlexFDO

Authors Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11549345

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Parameterized complexity of constraint satisfaction problems
• On the parameterized complexity of \((k,s)\)-SAT
• Parameterized complexity of weighted satisfiability problems
• Theory and Applications of Satisfiability Testing
• The complexity of satisfiability problems
• An exact and a randomized approach for the satisfiability problem

Cited in

(16)

• On the parameterized complexity of \((k,s)\)-SAT
• A perspective on certain polynomial-time solvable classes of satisfiability
• Improved exact algorithms for mildly sparse instances of MAX SAT
• Parameterized complexity of weighted satisfiability problems
• Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance
• Kernelization: new upper and lower bound techniques
• Succinct Permanent Is NEXP-Hard with Many Hard Instances
• Theory and Applications of Satisfiability Testing
• On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• Parameterized complexity and kernelizability of max ones and exact ones problems
• Parameterized complexity and kernelizability of Max Ones and Exact Ones problems
• On O(Tlog T) reduction from RAM computations to satisfiability
• Solving sparse instances of Max SAT via width reduction and greedy restriction

This page was built for publication: Mathematical Foundations of Computer Science 2005

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5492890)