• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
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
http://dx.doi.org/10.1007/3-540-54967-6_75
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

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    On the differential approximation of MIN SET COVER 
    Bazgan, Cristina; Monnot, Jérôme; Paschos, Vangelis; Serrière, Fabrice (2005) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Solving vertex cover, independent set and related problems by a Boltzmann machine 
    Paschos, Vangelis; Pekergin, Ferhan; Zissimopoulos, Vassilis (1992) Communication / Conférence
  • Vignette de prévisualisation
    Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximation 
    Ekim, Tinaz; Paschos, Vangelis (2004) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set 
    Paschos, Vangelis (1994) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo