Output details
11 - Computer Science and Informatics
Birkbeck College
Article title
Almost 2-SAT is fixed-parameter tractable
Type
D - Journal article
Title of journal
Journal of Computer and System Sciences
Article number
-
Volume number
75
Issue number
8
First page of article
435
ISSN of journal
00220000
Year of publication
2009
URL
-
Number of additional authors
1
Additional information
<12> We establish fixed-parameter tractability of a problem whose status was open for more than 10 years despite very active investigations. In the book "Invitation to fixed-parameter algorithms" by Rolf Niedermeier, the problem is mentioned as number 2 in the list of central challenges in parameterized algorithmics. This paper is an extended version of a conference paper presented at the International Colloquium on Algorithms, Languages an Programming (ICALP), 2008. There has been considerable follow up work by others, including three consecutive improvements of the runtime of algorithms solving this problem.
Interdisciplinary
-
Cross-referral requested
-
Research group
A - Computational Intelligence
Citation count
34
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
