NIST

vertex cover

(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

Implementation

(C, Fortran, and Mathematica)
Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 September 2014.
HTML page formatted Fri Feb 23 10:06:08 2018.

Cite this as:
Paul E. Black, "vertex cover", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/vertexcover.html