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>

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

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>

Constructor Summary

Constructors

Constructor and Description
BarYehudaEvenTwoApproxVCImpl()

Method Summary

Modifier and Type	Method and Description
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.

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

public BarYehudaEvenTwoApproxVCImpl()

Method Detail

getVertexCover

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

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:

a vertex cover