15 citations · 39 across the 8 of their papers we have counts for
6 papers · 1 filter
Maximum Balanced Subgraph Problem Parameterized Above Lower Bound
R. Crowston, G. Gutin, M. Jones +1
We consider graphs without loops or parallel edges in which every edge is assigned + or -. Such a signed graph is balanced if its vertex set can be partitioned into parts and…
Parameterized Study of the Test Cover Problem
R. Crowston, G. Gutin, M. Jones +2
We carry out a systematic study of a natural covering problem, used for identification across several areas, in the realm of parameterized complexity. In the {\sc Test Cover} probl…
Fixed-parameter tractability of satisfying beyond the number of variables
R. Crowston, G. Gutin, M. Jones +3
We consider a CNF formula as a multiset of clauses: . The set of variables of will be denoted by . Let denote the bipartite graph with parti…
Parameterizations of Test Cover with Bounded Test Sizes
Robert Crowston, Gregory Gutin, Mark Jones +2
In the {\sc Test Cover} problem we are given a hypergraph with , and we assume that is a test cover, i.e. for every pair…
Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound
Robert Crowston, Gregory Gutin, Mark Jones
An oriented graph is a directed graph without directed 2-cycles. Poljak and Turzík (1986) proved that every connected oriented graph on vertices and arcs contains an ac…
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…