| Calling Sequence | VertexCover(A)
| |||||||||
| Parameters |
| |||||||||
| Return Type | set | |||||||||
| Synopsis | The input to this algorithm is an undirected graph. An undirected graph is represented as a Graph data structure which should accept two selectors: Nodes and Edges. The Vertex Cover problem is finding the minimum set of vertices which "cover" all edges. That is a minimum size set of vertices such that each edge is incident to at least one of the vertices in this set. | |||||||||
The output is a set of the Nodes in the vertex cover. The algorithm computes a lower bound on the size of the vertex cover which is left in the global variable VertexCoverLowerBound. If this coincides with the size of the answer, it means that the answer is optimal. The global variable VertexCoverIterFactor may be assigned a non-negative number f. The algorithm will then run for f*n^2 iterations. If f=0 then only the greedy heuristic is run, and this is quite fast. The larger f, the more accurate the answers will be, and the more time the algorithm will consume. | ||||||||||
The Vertex Cover problem is closely related to the Clique problem. They can be related by the following formula: | ||||||||||
VertexCover(G) = NodeComplement(Clique(EdgeComplement(G))) | ||||||||||
| Examples | > VertexCover(PetersenGraph()); {1,2,3,6,8,10}
> VertexCoverLowerBound; 6 | |||||||||
| See also | BipartiteGraph, Clique, DrawGraph, Edge, EdgeComplement, Edges, FindConnectedComponents, Graph, Graph_Rand, InduceGraph, MaxCut, MaxEdgeWeightClique, MST, Nodes, Path, RegularGraph, ShortestPath, TetrahedronGraph | |||||||||