- java.lang.Object
-
- org.jgrapht.alg.vertexcover.RecursiveExactVCImpl<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
VertexCoverAlgorithm<V>
public class RecursiveExactVCImpl<V,E> extends java.lang.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)$
- Author:
- Joris Kinable
-
-
Nested Class Summary
Nested Classes Modifier and Type Class 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 Description RecursiveExactVCImpl(Graph<V,E> graph)
Constructs a new GreedyVCImpl instanceRecursiveExactVCImpl(Graph<V,E> graph, java.util.Map<V,java.lang.Double> vertexWeightMap)
Constructs a new GreedyVCImpl instance
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description VertexCoverAlgorithm.VertexCover<V>
getVertexCover()
Computes a vertex cover.
-
-
-
Method Detail
-
getVertexCover
public VertexCoverAlgorithm.VertexCover<V> getVertexCover()
Description copied from interface:VertexCoverAlgorithm
Computes a vertex cover.- Specified by:
getVertexCover
in interfaceVertexCoverAlgorithm<V>
- Returns:
- a vertex cover
-
-