Almost 2-SAT is fixed-parameter tractable
type: Item
instance of: scholarly article
title: Almost 2-SAT is fixed-parameter tractable
zbMATH Open document ID: 1184.68477
author: Igor Razgon
author: Barry O'Sullivan
published in: Journal of Computer and System Sciences
publication date: 2009-11-10T00:00:00Z
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5629239
zbMATH Keywords: fixed-parameter algorithms
zbMATH Keywords: satisfiability problems
zbMATH Keywords: separation problems
MaRDI profile type: Publication
full work available at URL: j.jcss.2009.04.002
OpenAlex ID: W1485150579
cites work: Q4500916
cites work: Improved Algorithms for the Feedback Vertex Set Problems
cites work: Improved exact algorithms for MAX-SAT
cites work: An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
cites work: Q3549698
cites work: Parameterized Approximability of the Disjoint Cycle Problem
cites work: SOFSEM 2006: Theory and Practice of Computer Science
cites work: Experimental and Efficient Algorithms
cites work: Parameterized complexity of finding subgraphs with hereditary properties.
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Parameterized graph separation problems
cites work: The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
cites work: Q5710169
cites work: Q4298260
cites work: Finding odd cycle transversals.
cites work: Algorithms - ESA 2003
DOI: 10.1016/J.JCSS.2009.04.002
Recommended article: Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
Recommended article: Theory and Applications of Satisfiability Testing
Recommended article: Fixed-Parameter Tractable Reductions to SAT
Recommended article: Fixed-Parameter Tractability of almost CSP Problem with Decisive Relations
Recommended article: A bottom-up algorithm for solving ♯2SAT
Recommended article: Solving satisfiability in less than \(2^ n\) steps
Recommended article: A bounded approximation for the minimum cost 2-sat problem
Recommended article: Q4501522
Recommended article: On semidefinite programming relaxations of \((2+p)\)-SAT
Recommended article: Fixed-Parameter Tractability of Satisfying beyond the Number of Variables
description: scientific article; zbMATH DE number 5629239