Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DOMINATING SET:
Reports tagged with Dominating Set:
TR17-186 | 29th November 2017
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi

#### On the Parameterized Complexity of Approximating Dominating Set

Revisions: 1

We study the parameterized complexity of approximating the $k$-Dominating Set (domset) problem where an integer $k$ and a graph $G$ on $n$ vertices are given as input, and the goal is to find a dominating set of size at most $F(k) \cdot k$ whenever the graph $G$ has a dominating ... more >>>

ISSN 1433-8092 | Imprint