Name
Title | ||
|---|---|---|
The complexity of connected dominating sets and total dominating sets with specified induced subgraphs |
Abstract | ||
|---|---|---|
Given a graph class G, it is natural to ask (i) whether a given graph G has a connected or a total dominating set whose induced subgraph is a member of G and (ii) whether G has such a set of cardinality at most a given threshold. We give sufficient conditions on G under which these two problems are NP-hard. This condition is fulfilled in a wide variety of classes of graphs. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.ipl.2012.09.002 | Inf. Process. Lett. |
Keywords | Field | DocType |
sufficient condition,wide variety,induced subgraph,connected dominating set,graph g,graph class g,total dominating set,specified induced subgraphs,computational complexity | Connected domination,Discrete mathematics,Graph,Combinatorics,Dominating set,Ask price,Induced subgraph,Cardinality,Connected dominating set,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
112 | 24 | 0020-0190 |
Citations | PageRank | References |
7 | 0.47 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oliver Schaudt | 1 | 95 | 21.74 |
| Rainer Schrader | 2 | 7 | 0.47 |