Dominating sets

dominating_set(g, DegreeDominatingSet())

Obtain a dominating set using a greedy heuristic.

Implementation Notes

A vertex is said to be dominated if it is in the dominating set or adjacent to a vertex in the dominating set. Initialise the dominating set to an empty set and iteratively choose the vertex that would dominate the most undominated vertices.

Performance

Runtime: $\mathcal{O}((|V|+|E|)*log(|V|))$ Memory: $\mathcal{O}(|V|)$ Approximation Factor: ln(maximum(degree(g)))+2

update_dominated!(degree_queue, v, dominated, in_dom_set)

Check if a vertex is already dominated. If not, make it dominated and update degree_queue by decreasing the priority of the vertices adjacent to v by 1.

dominating_set(g, MinimalDominatingSet(); rng=nothing, seed=nothing)

Find a set of vertices that constitutes a dominating set (all vertices in g are either adjacent to a vertex in the set or is a vertex in the set) and it is not possible to delete a vertex from the set without sacrificing the dominating property.

Implementation Notes

Initially, every vertex is in the dominating set. In some random order, we check if the removal of a vertex from the set will destroy the dominating property. If no, the vertex is removed from the dominating set.

Performance

Runtime: $\mathcal{O}(|V|+|E|)$ Memory: $\mathcal{O}(|V|)$

Optional Arguments

• rng=nothing: set the Random Number Generator.
• If seed >= 0, a random generator is seeded with this value.