(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 police 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 Black.
Entry modified 2 November 2020.
HTML page formatted Mon Nov 2 12:36:42 2020.
Cite this as:
Paul E. Black, "vertex cover", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 2 November 2020. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/vertexcover.html