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 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

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 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