# Dominating sets

*Graphs.jl* implements functions for dominating sets.

## Index

## Full docs

`Graphs.dominating_set`

— Method`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`

`Graphs.update_dominated!`

— Method`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.

`Graphs.dominating_set`

— Method`dominating_set(g, MinimalDominatingSet(); rng=nothing, seed=nothing)`

Find a set of vertices that consitute 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.