Definition: A set of vertices in an undirected graph where every edge connects at least one vertex. The vertex cover problem is to find a minimum size set and is NP-complete.
See also vertex coloring, covering.
Note: An illustration of vertex cover is posting the least number of polices to watch every street in a city. Clearly police should be at intersections. What's the smallest set of intersections?
To correspond to the vertex cover problem, streets must be straight. A curving street is divided into segments such that at any intersection, a person can see from that intersection to the next. Also, no street goes straight through an intersection.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 8 February 2007.
HTML page formatted Mon Nov 18 10:44:10 2013.
Cite this as:
Paul E. Black, "vertex cover", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 8 February 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/vertexcover.html