org.jgrapht.alg.vertexcover

Class BarYehudaEvenTwoApproxVCImpl<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MinimumVertexCoverAlgorithm<V,E>, MinimumWeightedVertexCoverAlgorithm<V,E>, VertexCoverAlgorithm<V>

public class BarYehudaEvenTwoApproxVCImpl<V,E>
extends Object
implements MinimumWeightedVertexCoverAlgorithm<V,E>, VertexCoverAlgorithm<V>

Implementation of the 2-opt algorithm for a minimum weighted vertex cover by R. Bar-Yehuda and S. Even. A linear time approximation algorithm for the weighted vertex cover problem. J. of Algorithms 2:198-203, 1981. The solution is guaranteed to be within $2$ times the optimum solution. An easier-to-read version of this algorithm can be found here: https://www.cs.umd.edu/class/spring2011/cmsc651/vc.pdf Note: this class supports pseudo-graphs Runtime: $O(|E|)$ This is a fast algorithm, guaranteed to give a $2$-approximation. A solution of higher quality (same approximation ratio) at the expensive of a higher runtime can be obtained using BarYehudaEvenTwoApproxVCImpl. TODO: Remove the UndirectedSubgraph dependency! Querying vertex degrees on these graphs is actually slow! This does affect the runtime complexity. Better would be to just work on a clone of the original graph!

Author:

Joris Kinable

Nested Class Summary

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

MinimumVertexCoverAlgorithm.VertexCover<V>, MinimumVertexCoverAlgorithm.VertexCoverImpl<V>

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

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

Constructor Summary

Constructors

Constructor and Description
BarYehudaEvenTwoApproxVCImpl() Deprecated. this constructor will be removed in the next release
BarYehudaEvenTwoApproxVCImpl(Graph<V,E> graph) Constructs a new BarYehudaEvenTwoApproxVCImpl instance where all vertices have uniform weights.
BarYehudaEvenTwoApproxVCImpl(Graph<V,E> graph, Map<V,Double> vertexWeightMap) Constructs a new BarYehudaEvenTwoApproxVCImpl instance

Method Summary

Modifier and Type	Method and Description
VertexCoverAlgorithm.VertexCover	getVertexCover() Computes a vertex cover.
MinimumVertexCoverAlgorithm.VertexCover<V>	getVertexCover(Graph<V,E> graph, Map<V,Double> vertexWeightMap) Deprecated. Replaced by getVertexCover()

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.alg.interfaces.MinimumWeightedVertexCoverAlgorithm

getVertexCover

Constructor Detail

BarYehudaEvenTwoApproxVCImpl

@Deprecated
public BarYehudaEvenTwoApproxVCImpl()

Deprecated. this constructor will be removed in the next release

Temporary constructor to ensure one-version-backwards-compatibility

BarYehudaEvenTwoApproxVCImpl

public BarYehudaEvenTwoApproxVCImpl(Graph<V,E> graph)

Constructs a new BarYehudaEvenTwoApproxVCImpl instance where all vertices have uniform weights.

Parameters:

graph - input graph

BarYehudaEvenTwoApproxVCImpl

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

Constructs a new BarYehudaEvenTwoApproxVCImpl instance

Parameters:

graph - input graph

vertexWeightMap - mapping of vertex weights

Method Detail

getVertexCover

public VertexCoverAlgorithm.VertexCover getVertexCover()

Description copied from interface: VertexCoverAlgorithm

Computes a vertex cover.

Specified by:

getVertexCover in interface VertexCoverAlgorithm<V>

Returns:

a vertex cover

getVertexCover

@Deprecated
public MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(Graph<V,E> graph,
                                                                             Map<V,Double> vertexWeightMap)

Deprecated. Replaced by getVertexCover()

Description copied from interface: MinimumWeightedVertexCoverAlgorithm

Computes a vertex cover; the weight of each vertex is provided in the in the vertexWeightMap.

Specified by:

getVertexCover in interface MinimumWeightedVertexCoverAlgorithm<V,E>

Parameters:

graph - the input graph

vertexWeightMap - map containing non-negative weights for each vertex

Returns:

vertex cover