Independent sets

independent_set(g, DegreeIndependentSet())

Obtain an independent set of g using a greedy heuristic based on the degree of the vertices.

Implementation Notes

A vertex is said to be valid if it is not in the independent set or adjacent to any vertex in the independent set. Initilalise the independent set to an empty set and iteratively choose the vertex that is adjacent to the fewest valid vertices in the independent set until all vertices are invalid.

Performance

Runtime: O((|V|+|E|)*log(|V|)) Memory: O(|V|)

independent_set(g, MaximalIndependentSet(); rng=nothing, seed=nothing)

Find a random set of vertices that are independent (no two vertices are adjacent to each other) and it is not possible to insert a vertex into the set without sacrificing the independence property.

Implementation Notes

Performs Approximate Maximum Independent Set once. Returns a vector of vertices representing the vertices in the independent set.

Performance

Runtime: O(|V|+|E|) Memory: O(|V|) Approximation Factor: maximum(degree(g))+1

Optional Arguments

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