build_cover_random {gor}

Random vertex covers

Description

Random algorithm for vertex-cover.

Usage

build_cover_random(G, N, p = 0.75)

Arguments

G

Graph.

N

Number of random vertex set to try.

p

Probability of each element to be selected.

Details

It builds N random vertex sets by inserting elements with probability p, and it verifies if the subset so chosen is a vertex cover by running is_cover on it. It is very difficult to find a good vertex cover in this way, so this algorithm is very inefficient and it finds no specially good covers.

Currently, this function is not exported. The random sampling performed by search_cover_random is faster and more efficient.

Value

A list with four components: $set contains the subset of V(g) representing the cover and $size contains the number of vertices of the cover; $found is the number of vertex covers found and $failed is the number of generated subset that were not vertex covers.

Author(s)

Cesar Asensio

Examples

n <- 25
g <- sample_gnp(n, p=0.25)  # Random graph
X5 <- build_cover_random(g,10000,p=0.65)
X5$size            # 19
plot_cover(X5, g)
X6 <- improve_cover_flip(g, X5)   # Improved : 17
plot_cover(X6, g)