Lesson plan
Efficient dominating set
by exactly one vertex in this set (colored by which one dominates it), including the vertices of the set, each of which dominates itself. In graph theory, an efficient dominating set (also called an e.d. set or independent perfect dominating set ) is a dominating set with the additional property that every vertex in the graph is dominated by exactly one vertex in the set. The efficient domination problem (ED problem) asks whether a given graph contains an efficient dominating set. The problem is NP-complete for general graphs and remains NP-complete even when restricted to 3-regular planar graphs.
Article summary
by exactly one vertex in this set (colored by which one dominates it), including the vertices of the set, each of which dominates itself. In graph theory, an efficient dominating set (also called an e.d. set or independent perfect dominating set ) is a dominating set with the additional property that every vertex in the graph is dominated by exactly one vertex in the set. The efficient domination problem (ED problem) asks whether a given graph contains an efficient dominating set. The problem is NP-complete for general graphs and remains NP-complete even when restricted to 3-regular planar graphs.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.