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:

VertexCoverAlgorithm<V>

public class BarYehudaEvenTwoApproxVCImpl<V,E>
extends Object
implements 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.VertexCoverAlgorithm

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

Constructor Summary

Constructors

Constructor and Description
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<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

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<V> getVertexCover()

Description copied from interface: VertexCoverAlgorithm

Computes a vertex cover.

Specified by:

getVertexCover in interface VertexCoverAlgorithm<V>

Returns:

a vertex cover