build_cut_greedy {gor}

Greedy algorithm aimed to build a large weight cut in a graph

Description

This routine uses a greedy algorithm to build a cut with large weight. This is a 2-approximation algorithm, which means that the weight of the cut returned by this algorithm is larger than half the maximum possible cut weight for a given graph.

Usage

build_cut_greedy(G, w = NA)

Arguments

G

Graph

w

Weight matrix (defaults to NA). It should be zero for those edges not in G

Details

The algorithm builds a vertex subset S a step a a time. It starts with S = c(v1), and with vertices v1 and v2 marked. Then it iterates from vertex v3 to vn checking if the weight of the edges joining vi with marked vertices belonging to S is less than the weight of the edges joining vi with marked vertices not belonging to S. If the former weight is less than the latter, then vi is adjoined to S. At the end of each iteration, vertex vi is marked. When all vertices are marked the algorithm ends and S is already built.

Value

A list with four components: $set contains the subset of V(g) representing the cut, $size contains the number of edges of the cut, $weight contains the weight of the cut (which coincides with $size if w is NA) and $cut contains the edges of the cut, joining vertices inside $set with vertices outside $set.

Author(s)

Cesar Asensio

References

Korte, Vygen Combinatorial Optimization. Theory and Algorithms.

See Also

build_cut_random builds a random cut, improve_cut_flip uses local search to improve a cut obtained by other methods, compute_cut_weight computes cut size, weight and edges, plot_cut plots a cut.

Examples

## Example with known maximum cut
K10 <- make_full_graph(10)   # Max cut of size 25
c0 <- build_cut_greedy(K10)
c0$size  # 25
plot_cut(c0, K10)

## Max-cut of a random graph
set.seed(1)
n <- 25
g <- sample_gnp(n, p=0.25)
c2 <- build_cut_greedy(g)
c2$size   # 59
plot_cut(c2, g)