Thumbnail - Request a copy

A theorem on the approximation of set cover and vertex cover

Paschos, Vangelis (1991), A theorem on the approximation of set cover and vertex cover, dans Biswas, Somenath; Nori, Kesav V., Foundations of Software Technology and Theoretical Computer Science 11th Conference, New Delhi, India, December 17-19, 1991. Proceedings, Springer : Berlin, p. 278-287. http://dx.doi.org/10.1007/3-540-54967-6_75

Type
Communication / Conférence
Date
1991
Titre du colloque
11th Conference on Foundations of Software Technology and Theoretical Computer Science (FCT&TCS'91)
Date du colloque
1991-12
Ville du colloque
New Delhi
Pays du colloque
Inde
Titre de l'ouvrage
Foundations of Software Technology and Theoretical Computer Science 11th Conference, New Delhi, India, December 17-19, 1991. Proceedings
Auteurs de l’ouvrage
Biswas, Somenath; Nori, Kesav V.
Éditeur
Springer
Titre de la collection
Lecture Notes in Computer Science; 560
Ville d’édition
Berlin
Isbn
978-3-540-54967-3
Nombre de pages
420
Pages
278-287
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Paschos, Vangelis
Résumé (EN)
An approximation result is given, connecting two well known combinatorial problems, the Set Cover and the Vertex Cover. This result constitutes an improvement of the existing ratio for the latter, on a large and intuitive class of graphs, provided that an approximation algorithm exists for the former.
Mots-clés
approximation algorithms; Vertex cover; Set cover