Dominating sets
Graphs.jl implements functions for dominating sets.
Index
Full docs
Graphs.dominating_set
— Methoddominating_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
Graphs.update_dominated!
— Methodupdate_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.
Graphs.dominating_set
— Methoddominating_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.