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érenceDate
1991Titre du colloque
11th Conference on Foundations of Software Technology and Theoretical Computer Science (FCT&TCS'91)Date du colloque
1991-12Ville du colloque
New DelhiPays du colloque
IndeTitre de l'ouvrage
Foundations of Software Technology and Theoretical Computer Science 11th Conference, New Delhi, India, December 17-19, 1991. ProceedingsAuteurs de l’ouvrage
Biswas, Somenath; Nori, Kesav V.Éditeur
Springer
Titre de la collection
Lecture Notes in Computer Science; 560Ville d’édition
Berlin
Isbn
978-3-540-54967-3
Nombre de pages
420Pages
278-287
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Paschos, VangelisRé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 coverPublications associées
Affichage des éléments liés par titre et auteur.
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Bazgan, Cristina; Monnot, Jérôme; Paschos, Vangelis; Serrière, Fabrice (2005) Article accepté pour publication ou publié
-
Paschos, Vangelis; Pekergin, Ferhan; Zissimopoulos, Vassilis (1992) Communication / Conférence
-
Ekim, Tinaz; Paschos, Vangelis (2004) Article accepté pour publication ou publié
-
Paschos, Vangelis (1994) Article accepté pour publication ou publié