Class MinVertexCoverExp

java.lang.Object
es.urjc.etsii.grafo.experiment.AbstractExperiment<MSTSolution, MSTInstance>
es.urjc.etsii.grafo.graphs.experiments.MinVertexCoverExp
public class MinVertexCoverExp extends AbstractExperiment<MSTSolution, MSTInstance>
Minimum Vertex Cover (MVC), solved with CMSA (Construct, Merge, Solve & Adapt). Unlike MST/Shortest Paths, MVC is NP-hard: there is no known polynomial exact algorithm, which is exactly the kind of problem CMSA targets. See MVCConstructive for the probabilistic construction used to sample candidate vertices, and MVCExactCoverSolver for the exact method used to solve the restricted sub-instance at every iteration.

  • Constructor Details

    • MinVertexCoverExp

      public MinVertexCoverExp()

  • Method Details

    • getAlgorithms

      public List<Algorithm<MSTSolution, MSTInstance>> getAlgorithms()
      Description copied from class: AbstractExperiment
      Get list of algorithms defined in this experiment. Each experiment can define a different set of algorithms. Although the same algorithm can be used several times in the same experiment, if you return the same configuration for the same algorithm an exception will be thrown.
      Specified by:
      getAlgorithms in class AbstractExperiment<MSTSolution, MSTInstance>
      Returns:
      list of algorithms defined in this experiment