Expand description
Dominating set algorithms (ALGO-VC-003).
A dominating set is a subset D of vertices such that every vertex is either in D or adjacent to at least one vertex in D. Finding a minimum dominating set is NP-hard; we provide a greedy O(ln n)-approximation.
The greedy algorithm repeatedly picks the vertex that dominates the most currently-undominated vertices (including itself).
Functionsยง
- is_
dominating_ set - Check whether a set of vertices forms a valid dominating set.
- minimum_
dominating_ set - Compute an approximate minimum dominating set using a greedy heuristic.