38 citations · 83 across the 17 of their papers we have counts for
5 papers · 1 filter
Max-Cut Parameterized Above the Edwards-Erdős Bound
Robert Crowston, Mark Jones, Matthias Mnich
We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut above the Edwards-Erdős bound is fixed-parameter tractable: we give an a…
Parameterized Complexity of Satisfying Almost All Linear Equations over
R. Crowston, G. Gutin, M. Jones +1
The problem MaxLin2 can be stated as follows. We are given a system of equations in variables , where each equation is is assigned…
Parameterized Complexity of MaxSat Above Average
Robert Crowston, Gregory Gutin, Mark Jones +2
In MaxSat, we are given a CNF formula with variables and clauses and asked to find a truth assignment satisfying the maximum number of clauses. Let be th…
Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments
Robert Crowston, Gregory Gutin, Mark Jones +1
In the problem {\sc Min-DESC}, we are given a digraph and an integer , and asked if there exists a set of at most arcs in , such that if we remove the arcs of $A…
Simultaneously Satisfying Linear Equations Over : MaxLin2 and Max--Lin2 Parameterized Above Average
R. Crowston, M. Fellows, G. Gutin +4
In the parameterized problem \textsc{MaxLin2-AA}[], we are given a system with variables consisting of equations of the form , where $x_i,b…