Statements (28)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
graph
|
| gptkbp:application |
social network analysis
network design resource placement |
| gptkbp:complexity |
NP-complete
|
| gptkbp:defines |
A dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is adjacent to at least one member of D.
|
| gptkbp:dominationNumber |
size of minimum dominating set
|
| gptkbp:field |
discrete mathematics
graph theory |
| gptkbp:generalizes |
vertex cover
|
| gptkbp:hasVariant |
connected dominating set
independent dominating set total dominating set weighted dominating set |
| https://www.w3.org/2000/01/rdf-schema#label |
Dominating Set
|
| gptkbp:introducedIn |
graph theory literature
|
| gptkbp:minimumDominatingSet |
smallest possible dominating set in a graph
|
| gptkbp:notation |
γ(G) for domination number
|
| gptkbp:NP-complete |
minimum dominating set problem
|
| gptkbp:relatedTo |
independent set
vertex cover minimum dominating set |
| gptkbp:supportsAlgorithm |
greedy algorithm
approximation algorithm |
| gptkbp:usedIn |
wireless networks
biological networks |
| gptkbp:bfsParent |
gptkb:Vertex_Cover
|
| gptkbp:bfsLayer |
7
|