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 E. Black.
Entry modified 8 February 2007.
HTML page formatted Tue Dec 6 16:16:33 2011.
Cite this as:
Paul E. Black, "vertex cover", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 8 February 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/vertexcover.html