Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)

DOI10.1007/978-3-540-70575-8_45MaRDI QIDQ3521946zbMATH OpenOpenAlexFDO

Authors Igor Razgon, Barry O'Sullivan

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_45

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• Almost 2-SAT is fixed-parameter tractable
• Theory and Applications of Satisfiability Testing
• Fixed-parameter tractable reductions to SAT
• Approximating satisfiable satisfiability problems (extended abstract)
• On semidefinite programming relaxations of \((2+p)\)-SAT
• A bounded approximation for the minimum cost 2-sat problem
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• Fixed-parameter tractability of almost CSP problem with decisive relations
• Mathematical Foundations of Computer Science 2005
• Parameterized and Exact Computation

Cited in

(11)

• Parameterizing above or below guaranteed values
• Almost 2-SAT is fixed-parameter tractable
• On the Approximability of Splitting-SAT in 2-CNF Horn Formulas
• Fixed-parameter tractability of almost CSP problem with decisive relations
• Clustering with Local Restrictions
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Separator-based data reduction for signed graph balancing
• Vertex cover problem parameterized above and below tight bounds
• Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability
• On the parameterized vertex cover problem for graphs with perfect matching
• Constant ratio fixed-parameter approximation of the edge multicut problem

This page was built for publication: Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)

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