org.jgrapht.alg.vertexcover

Class RecursiveExactVCImpl<V,E>

java.lang.Object

org.jgrapht.alg.vertexcover.RecursiveExactVCImpl<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

VertexCoverAlgorithm<V>

public class RecursiveExactVCImpl<V,E>
extends Object
implements VertexCoverAlgorithm<V>

Finds a minimum vertex cover in a undirected graph. The implementation relies on a recursive algorithm. At each recursive step, the algorithm picks a unvisited vertex v and distinguishes two cases: either v has to be added to the vertex cover or all of its neighbors. In pseudo code, the algorithm (simplified) looks like this:

 
  $VC(G)$:
  if $V = \emptyset$ then return $\emptyset$
  Choose an arbitrary node $v \in G$
  $G1 := (V − v, \left{ e \in E | v \not \in e \right})$
  $G2 := (V − v − N(v), \left{ e \in E | e \cap (N(v) \cup v)= \empty \right})$
  if $|v \cup VC(G1)| \leq |N(v) \cup VC(G2)|$ then
    return $v \cup VC(G1)$
  else
    return $N(v) \cup VC(G2)$
 
 

To speed up the implementation, memoization and a bounding procedure are used. The current implementation solves instances with 150-250 vertices efficiently to optimality. TODO JK: determine runtime complexity and add it to class description. TODO JK: run this class through a performance profiler

Author:

Joris Kinable

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	RecursiveExactVCImpl.BitSetCover Helper class which represents a vertex cover as a space efficient BitSet

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexCoverAlgorithm

VertexCoverAlgorithm.VertexCover<V>, VertexCoverAlgorithm.VertexCoverImpl<V>

Constructor Summary

Constructors

Constructor and Description
RecursiveExactVCImpl(Graph<V,E> graph) Constructs a new GreedyVCImpl instance
RecursiveExactVCImpl(Graph<V,E> graph, Map<V,Double> vertexWeightMap) Constructs a new GreedyVCImpl instance

Method Summary

Modifier and Type	Method and Description
VertexCoverAlgorithm.VertexCover<V>	getVertexCover() Computes a vertex cover.

Methods inherited from class java.lang.Object

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

Constructor Detail

RecursiveExactVCImpl

public RecursiveExactVCImpl(Graph<V,E> graph)

Constructs a new GreedyVCImpl instance

Parameters:

graph - input graph

RecursiveExactVCImpl

public RecursiveExactVCImpl(Graph<V,E> graph,
                            Map<V,Double> vertexWeightMap)

Constructs a new GreedyVCImpl instance

Parameters:

graph - input graph

vertexWeightMap - mapping of vertex weights

Method Detail

getVertexCover

public VertexCoverAlgorithm.VertexCover<V> getVertexCover()

Description copied from interface: VertexCoverAlgorithm

Computes a vertex cover.

Specified by:

getVertexCover in interface VertexCoverAlgorithm<V>

Returns:

a vertex cover