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

DOI10.1007/978-3-540-70575-8_45zbMath1153.68397OpenAlexW1503863201MaRDI QIDQ3521946

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)

Related Items

Separator-based data reduction for signed graph balancing ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Vertex cover problem parameterized above and below tight bounds ⋮ Clustering with Local Restrictions ⋮ Constant ratio fixed-parameter approximation of the edge multicut problem ⋮ Parameterizing above or below guaranteed values ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems