4 citations · 4 across the 1 of their papers we have counts for
2 papers
cs.DS2008★ 4 cited
Almost 2-SAT is Fixed-Parameter Tractable
Igor Razgon, Barry O'Sullivan
We consider the following problem. Given a 2-CNF formula, is it possible to remove at most clauses so that the resulting 2-CNF formula is satisfiable? This problem is known to…
cs.DS2007
Directed Feedback Vertex Set is Fixed-Parameter Tractable
Igor Razgon, Barry O'Sullivan
We resolve positively a long standing open question regarding the fixed-parameter tractability of the parameterized Directed Feedback Vertex Set problem. In particular, we propose…