Vertex cover
Graphs.jl provides some algorithms to find vertex covers.
Index
Full docs
Graphs.vertex_cover
— Methodvertex_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
Graphs.vertex_cover
— Methodvertex_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.