agape.algos

Class MVC<V,E>

java.lang.Object

agape.algos.Algorithms<V,E>

agape.algos.MVC<V,E>

Type Parameters:

V - Vertices type

E - Edges type

public class MVC<V,E>
extends Algorithms<V,E>

This class implements algorithms for solving the Minimum Vertex Cover problem. The problem consists in finding the minimum set of vertices such that any edge is incident at one of the vertex of the computed set. !! WARNING !! These algorithms work ONLY on undirected graphs.

Author:

V. Levorato, J.-F. Lalande, P. Berthome

Constructor Summary

Constructors

Constructor and Description
MVC(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory)

Method Summary

Methods

Modifier and Type	Method and Description
java.util.Set<V>	getVertexCoverSolution() Returns the last computed vertex cover set, null if the called Parameterized algorithms cannot find such a set.
java.util.Set<V>	greedyCoverMaxDegree(edu.uci.ics.jung.graph.Graph<V,E> g) Finds a greedy approximation for a minimal vertex cover of a specified graph.
boolean	kVertexCoverBruteForce(edu.uci.ics.jung.graph.Graph<V,E> g, int k) Returns true if a vertex cover of size k exists in graph G.
boolean	kVertexCoverBussGoldsmith(edu.uci.ics.jung.graph.Graph<V,E> g, int k) Returns true if a vertex cover of size k exists in graph G.
boolean	kVertexCoverDegreeBranchingStrategy(edu.uci.ics.jung.graph.Graph<V,E> g, int k) Returns true if a vertex cover of size k exists in graph G.
boolean	kVertexCoverNiedermeier(edu.uci.ics.jung.graph.Graph<V,E> g, int k) Returns true if a vertex cover of size k exists in graph G.
java.util.Set<V>	twoApproximationCover(edu.uci.ics.jung.graph.Graph<V,E> g) Finds a 2-approximation for a minimal vertex cover of the specified graph.

Methods inherited from class agape.algos.Algorithms

getEdgeFactory, getGraphFactory, getVertexFactory, setEdgeFactoy, setGraphFactoy, setVertexFactoy

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MVC

public MVC(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory)

Method Detail

getVertexCoverSolution

public java.util.Set<V> getVertexCoverSolution()

Returns the last computed vertex cover set, null if the called Parameterized algorithms cannot find such a set.

Returns:

a vertex cover (null if there is no solution)

twoApproximationCover

public java.util.Set<V> twoApproximationCover(edu.uci.ics.jung.graph.Graph<V,E> g)

Finds a 2-approximation for a minimal vertex cover of the specified graph. The algorithm promises a cover that is at most double the size of a minimal cover. The algorithm takes O(|E|) time.

Parameters:

g - the graph for which vertex cover approximation has to be found

Returns:

a set of vertices which is a vertex cover for the specified graph.

greedyCoverMaxDegree

public java.util.Set<V> greedyCoverMaxDegree(edu.uci.ics.jung.graph.Graph<V,E> g)

Finds a greedy approximation for a minimal vertex cover of a specified graph. At each iteration, the algorithm picks the vertex with the highest degree and adds it to the cover, until all edges are covered.

Parameters:

g - the graph for which vertex cover approximation has to be found

Returns:

a set of vertices which is a vertex cover for the specified graph.

kVertexCoverBruteForce

public boolean kVertexCoverBruteForce(edu.uci.ics.jung.graph.Graph<V,E> g,
                             int k)

Returns true if a vertex cover of size k exists in graph G. The complexity of this method is O(C_k^n) (exhaustive search). This algorithm test exhaustively all the combinations of k vertices among n. The principle is to test all the sets of size k: we build recursively these sets by choosing a new vertex to add in the set. When all the neighborhood of the set covers the graph, we stop if the size of the set is less than k.

Parameters:

g - graph

k - vertex cover size

Returns:

true if G contains a vertex cover of size k, else returns false.

kVertexCoverDegreeBranchingStrategy

public boolean kVertexCoverDegreeBranchingStrategy(edu.uci.ics.jung.graph.Graph<V,E> g,
                                          int k)

Returns true if a vertex cover of size k exists in graph G. The comupted set contains a cover of size at most k at the end of the algorithm. This method uses Degree-Branching-Strategy (DBS) and has a time complexity in O(1.47^k).

Parameters:

g - graph

k - vertex cover size

Returns:

true if G contains a vertex cover of size k, else returns false.

kVertexCoverBussGoldsmith

public boolean kVertexCoverBussGoldsmith(edu.uci.ics.jung.graph.Graph<V,E> g,
                                int k)

Returns true if a vertex cover of size k exists in graph G. This method reduces a graph instance in polynomial time in order to find a vertex cover by kernelization using Buss and Goldsmith reduction ("Nondeterminism within P", 1993).

Parameters:

g - graph

k - vertex cover size

Returns:

true if G contains a vertex cover of size k, else returns false.

kVertexCoverNiedermeier

public boolean kVertexCoverNiedermeier(edu.uci.ics.jung.graph.Graph<V,E> g,
                              int k)

Returns true if a vertex cover of size k exists in graph G. The computed set contains a cover of size at most k at the end of the algorithm. This method is an implementation of Niedermeier algorithm "Invitation to Fixed Parameter Algorithms", 2006, pages 98-101 which time complexity is O(1.33^k).

Parameters:

g - graph

k - vertex cover size

Returns:

true if G contains a vertex cover of size k, else returns false.