Name
Abstract | ||
|---|---|---|
Given two sets 驴, ρ of nonnegative integers, a set S of vertices of a graph G is (驴,ρ)-dominating if |S 驴 N(v)| 驴 驴 for every vertex v 驴 S, and |S 驴 N(v)| 驴 ρ for every v 驴 S. This concept, introduced by Telle in 1990's, generalizes and unifies several variants of graph domination studied separately before. We study the parameterized complexity of (驴,ρ)-domination in this general setting. Among other results we show that existence of a (驴,ρ)-dominating set of size k (and at most k) are W[1]-complete problems (when parameterized by k) for any pair of finite sets 驴 and ρ. We further present results on dual parametrization by n 驴 k, and results on certain infinite sets (in particular for 驴, ρ being the sets of even and odd integers). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.dam.2010.11.012 | Discrete Applied Mathematics |
Keywords | Field | DocType |
complete problem,general setting,parameterized complexity,size k,graph g,dual parameterization,finite set,certain infinite set,generalized domination problem,vertex v,graph domination | Integer,Discrete mathematics,Graph,Combinatorics,Parameterized complexity,Finite set,Parametrization,Vertex (geometry),Infinite set,Mathematics | Journal |
Volume | Issue | ISSN |
160 | 6 | Discrete Applied Mathematics |
Citations | PageRank | References |
8 | 0.50 | 28 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petr A. Golovach | 1 | 766 | 83.25 |
| Jan Kratochvíl | 2 | 1751 | 151.84 |
| OndřEj Suchý | 3 | 66 | 4.52 |