gor (version 2.0)

build_cover_greedy: Greedy algorithm for vertex cover in a graph

Description

This routine uses a greedy algorithm to build a cover selecting the highest degree vertex first and removing its incident edges.

Usage

build_cover_greedy(G)

Value

A list with two components: $set contains the cover, $size contains the number of vertices of the cover.

Arguments

G

Graph

Author

Cesar Asensio

Details

This algorithm builds a vertex cover since no edge remains to be covered when it returns. However, it is no guaranteed that the cover found by this algorithm has minimum cardinality.

References

Korte, Vygen Combinatorial Optimization. Theory and Algorithms.

See Also

is_cover checks if a vertex subset is a vertex cover, build_cover_approx builds a cover using a 2-approximation algorithm, improve_cover_flip improves a cover using local search, search_cover_random looks for a random cover of fixed size, search_cover_ants looks for a random cover using a version of the ant-colony optimization heuristic, find_cover_BB finds covers using a branch-and-bound technique, plot_cover plots a cover.

Examples

library(igraph)
## Example with known cover
K25 <- make_full_graph(25)   # Cover of size 24
X0 <- build_cover_greedy(K25)
X0$size  # 24
plot_cover(X0, K25)
plot_cover(list(set = c(1,2), size = 2), K25)

## Vertex-cover of a random graph
set.seed(1)
n <- 25
g <- sample_gnp(n, p=0.25)
X1 <- build_cover_greedy(g)
X1$size   # 17
plot_cover(X1, g)