V
- the graph vertex typeE
- the graph edge typepublic class RecursiveExactVCImpl<V,E> extends Object implements MinimumWeightedVertexCoverAlgorithm<V,E>
VC(G):
if V = ∅ then return ∅
Choose an arbitrary node v ∈ G
G1 := (V − {v}, { e ∈ E | v ∈/ e })
G2 := (V − {v} − N(v), { e ∈ E | e ∩ (N(v) ∪ {v})= ∅ })
if |{v} ∪ VC(G1)| ≤ |N(v) ∪ VC(G2)| then
return {v} ∪ VC(G1)
else
return N(v) ∪ 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 profilerModifier and Type | Class and Description |
---|---|
protected class |
RecursiveExactVCImpl.BitSetCover
Helper class which represents a vertex cover as a space efficient BitSet
|
MinimumVertexCoverAlgorithm.VertexCover<V>, MinimumVertexCoverAlgorithm.VertexCoverImpl<V>
Constructor and Description |
---|
RecursiveExactVCImpl() |
Modifier and Type | Method and Description |
---|---|
MinimumVertexCoverAlgorithm.VertexCover<V> |
getVertexCover(UndirectedGraph<V,E> graph)
Computes a vertex cover; all vertices are considered to have equal weight.
|
MinimumVertexCoverAlgorithm.VertexCover<V> |
getVertexCover(UndirectedGraph<V,E> graph,
Map<V,Double> vertexWeightMap)
Computes a vertex cover; the weight of each vertex is provided in the in the
vertexWeightMap . |
public MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(UndirectedGraph<V,E> graph)
MinimumWeightedVertexCoverAlgorithm
getVertexCover
in interface MinimumVertexCoverAlgorithm<V,E>
getVertexCover
in interface MinimumWeightedVertexCoverAlgorithm<V,E>
graph
- the graphpublic MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(UndirectedGraph<V,E> graph, Map<V,Double> vertexWeightMap)
MinimumWeightedVertexCoverAlgorithm
vertexWeightMap
.getVertexCover
in interface MinimumWeightedVertexCoverAlgorithm<V,E>
graph
- the input graphvertexWeightMap
- map containing non-negative weights for each vertexCopyright © 2017. All rights reserved.