Package com.jgalgo

Interface VertexCover

public interface VertexCover

Minimum weighted vertex cover algorithm.

Given a graph \(G=(V,E)\) a vertex cover is a set \(S \subseteq V\) for which for any edge \((u,v) \in E\) at least one of \(u\) or \(v\) are in \(S\). Given a vertex weight function \(w:V \rightarrow R\), the weight of a vertex cover is the weight sum of the vertices in the cover. The minimum vertex cover is the vertex cover with the minimum weight.

Note that finding the actual minimum vertex cover is an NP-hard problem, even for a weight function that assign \(1\) to each vertex. Therefore, algorithms implementing this interface provide an approximation for the actual optimal solution.

Author:

Barak Ugav

See Also:

Wikipedia

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	VertexCover.Builder	A builder for VertexCover algorithms.
static interface	VertexCover.Result	A result object of VertexCover computation.

Method Summary

Modifier and Type	Method	Description
VertexCover.Result	computeMinimumVertexCover(Graph g, WeightFunction w)	Compute a minimum vertex cover of a graph with respect to a vertex weight function.
static VertexCover.Builder	newBuilder()	Create a new vertex cover algorithm builder.

Method Detail

computeMinimumVertexCover

VertexCover.Result computeMinimumVertexCover(Graph g,
                                             WeightFunction w)

Compute a minimum vertex cover of a graph with respect to a vertex weight function.

Note that finding the minimum vertex cover is an NP-hard problem, therefore the result of this function is an approximation of the optimal solution.

Parameters:

g - a graph

w - a vertex weight function

Returns:

a minimum vertex cover

newBuilder

static VertexCover.Builder newBuilder()

Create a new vertex cover algorithm builder.

This is the recommended way to instantiate a new VertexCover object.

Returns:

a new builder that can build VertexCover objects