38 citations · 83 across the 17 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…
Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
J. Crampton, R. Crowston, G. Gutin +2
The workflow satisfiability problem is concerned with determining whether it is possible to find an allocation of authorized users to the steps in a workflow in such a way that all…
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…