Module org.jgrapht.core
Package 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

  • Constructor Details

    • 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 Details