Document Type
Article
Department
Computer Science (HMC)
Publication Date
1995
Abstract
Consider a computer network represented by an undirected graph where the vertices represent computer nodes and the edges represent links between the nodes. Since some of the links in the network may become faulty, link testing devices are placed at some of the nodes. A tester at a particular node can test all links incident to that node. Since the testers are expensive, however, we wish to deploy the minimum number of these devices such that every link is incidient to at least one node containing a tester. In graph theoretic terms, a vertex cover is a subset of the vertices such that every edge is incident to at least one vertex in this set. Our objective then is to find a minimum vertex cover. This is known as the vertex cover problem.
Rights Information
© 1995 Mathematical Association of America
Recommended Citation
R. Libeskind-Hadas, “Approximation Algorithms: Good Solutions to Hard Problems,”The American Mathematical Monthly, Vol. 102, No. 1, January 1995, pp. 57-61.
