Name
Abstract | ||
|---|---|---|
In 1994, Telle introduced the following notion of domination, which generalizes many domination-type graph invariants. Let @s and @r be two sets of non-negative integers. A vertex subset S@?V of an undirected graph G=(V,E) is called a (@s,@r)-dominating set of G if |N(v)@?S|@?@s for all v@?S and |N(v)@?S|@?@r for all v@?V@?S. In this paper, we prove that decision, optimization, and counting variants of ({p},{q})-domination are solvable in time 2^|^V^|^/^2@?|V|^O^(^1^). We also show how to extend these results for infinite @s={p+m@?@?:@?@?N"0} and @r={q+m@?@?:@?@?N"0}. For the case |@s|+|@r|=3, these problems can be solved in time 3^|^V^|^/^2@?|V|^O^(^1^), and similarly to the case |@s|=|@r|=1 it is possible to extend the algorithm for some infinite sets. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.ipl.2009.03.023 | Inf. Process. Lett. |
Keywords | Field | DocType |
vertex subset,generalized domination,undirected graph,non-negative integer,following notion,infinite set,exact algorithm,domination-type graph invariants,dominating set | Integer,Discrete mathematics,Graph,Combinatorics,Dominating set,Search algorithm,Vertex (geometry),sort,Algorithm,Infinite set,Invariant (mathematics),Mathematics | Journal |
Volume | Issue | ISSN |
109 | 14 | 0020-0190 |
Citations | PageRank | References |
3 | 0.40 | 6 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fedor V. Fomin | 1 | 3139 | 192.21 |
| Petr A. Golovach | 2 | 766 | 83.25 |
| Jan Kratochvíl | 3 | 1751 | 151.84 |
| Dieter Kratsch | 4 | 1957 | 146.89 |
| Mathieu Liedloff | 5 | 243 | 24.23 |