is_cover: Check vertex cover

In gor: Algorithms for the Subject Graphs and Network Optimization

Check vertex cover

Description

Check if some vertex subset of a graph covers all its edges.

Usage

is_cover(X, eG)

Arguments

X	Vertex subset to check.
eG	Edgelist of the graph as returned by as_edgelist

Details

The routine simply goes through the edge list of the graph to see if both ends of each edge are inside the vertex subset to be checked. When an edge with both ends ouside X is encountered, the routine returns FALSE; otherwise, it returns TRUE.

Value

Boolean: TRUE if X is a vertex cover of the graph represented by eG, FALSE otherwise.

Author(s)

Cesar Asensio

See Also

build_cover_greedy builds a cover using a greedy heuristic, 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

set.seed(1)
n <- 25
g <- sample_gnp(n, p=0.25)  # Random graph
eg <- as_edgelist(g)

X1 <- build_cover_greedy(g)
is_cover(X1$set, eg)   # TRUE
is_cover(c(1:10),eg)   # FALSE
plot_cover(list(set = 1:10, size = 10), g)  # See uncovered edges

gor documentation built on May 4, 2023, 1:06 a.m.