121 citations · 360 across the 111 of their papers we have counts for
9 papers · 1 filter
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…
Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan +2
We study the parameterized complexity of the directed variant of the classical {\sc Steiner Tree} problem on various classes of directed sparse graphs. While the parameterized comp…
Kernels for (connected) Dominating Set on graphs with Excluded Topological subgraphs
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh +1
We give the first linear kernels for the (Connected) Dominating Set problems on H-topological minor free graphs. We prove the existence of polynomial time algorithms that, for a gi…
Don't Be Strict in Local Search!
Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak +2
Local Search is one of the fundamental approaches to combinatorial optimization and it is used throughout AI. Several local search algorithms are based on searching the k-exchange…
Beyond Max-Cut: λ-Extendible Properties Parameterized Above the Poljak-Turzík Bound
Matthias Mnich, Geevarghese Philip, Saket Saurabh +1
Poljak and Turzík (Discrete Math. 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any…