Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Approximation Algorithms: Good Solutions To Hard Problems, Ran Libeskind-Hadas
Approximation Algorithms: Good Solutions To Hard Problems, Ran Libeskind-Hadas
All HMC Faculty Publications and Research
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 …