V- the graph vertex type
E- the graph edge type
public class GreedyVCImpl<V,E> extends Object implements VertexCoverAlgorithm<V>
|Constructor and Description|
Constructs a new GreedyVCImpl instance where all vertices have uniform weights.
Constructs a new GreedyVCImpl instance
|Modifier and Type||Method and Description|
Finds a greedy solution to the minimum weighted vertex cover problem.
public GreedyVCImpl(Graph<V,E> graph)
graph- input graph
public VertexCoverAlgorithm.VertexCover<V> getVertexCover()
weight(v)/degree(v)and adds it to the cover. Next vertex v and all edges incident to it are removed. The process repeats until all vertices are covered. Runtime: O(|E|*log|V|)
Copyright © 2019. All rights reserved.