Vertex cover

vertex_cover(g, DegreeVertexCover())

Obtain a vertex cover using a greedy heuristic.

Implementation Notes

An edge is said to be covered if it has at least one end-point in the vertex cover. Initialise the vertex cover to an empty set and iteratively choose the vertex with the most uncovered edges.

Performance

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

Examples

julia> using Graphs

julia> vertex_cover(path_graph(3), DegreeVertexCover())
1-element Vector{Int64}:
 2

julia> vertex_cover(cycle_graph(3), DegreeVertexCover())
2-element Vector{Int64}:
 1
 3

vertex_cover(g, RandomVertexCover(); rng=nothing, seed=nothing)

Find a set of vertices such that every edge in g has some vertex in the set as atleast one of its end point.

Implementation Notes

Performs Approximate Minimum Vertex Cover once. Returns a vector of vertices representing the vertices in the Vertex Cover.

Performance

Runtime: O(|V|+|E|) Memory: O(|E|) Approximation Factor: 2

Optional Arguments

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