• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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, in 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
Conference title
11th Conference on Foundations of Software Technology and Theoretical Computer Science (FCT&TCS'91)
Conference date
1991-12
Conference city
New Delhi
Conference country
Inde
Book title
Foundations of Software Technology and Theoretical Computer Science 11th Conference, New Delhi, India, December 17-19, 1991. Proceedings
Book author
Biswas, Somenath; Nori, Kesav V.
Publisher
Springer
Series title
Lecture Notes in Computer Science; 560
Published in
Berlin
ISBN
978-3-540-54967-3
Number of pages
420
Pages
278-287
Publication identifier
http://dx.doi.org/10.1007/3-540-54967-6_75
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Abstract (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.
Subjects / Keywords
approximation algorithms; Vertex cover; Set cover

Related items

Showing items related by title and author.

  • Thumbnail
    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é
  • Thumbnail
    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é
  • Thumbnail
    Solving vertex cover, independent set and related problems by a Boltzmann machine 
    Paschos, Vangelis; Pekergin, Ferhan; Zissimopoulos, Vassilis (1992) Communication / Conférence
  • Thumbnail
    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é
  • Thumbnail
    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
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo