(classic problem)
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.
Author: PEB
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
