Date
1991
Collection title
Lecture Notes in Computer Science560
Dewey
Recherche opérationnelle
Sujet
approximation algorithms; Vertex cover; Set cover
Conference name
11th Conference on Foundations of Software Technology and Theoretical Computer Science (FCT&TCS'91)
Conference date
12-1991
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
Author
Biswas, Somenath; Nori, Kesav V.
Publisher
Springer
Publisher city
Berlin
Year
1991
Pages number
420
ISBN
978-3-540-54967-3
Type
Communication / Conférence
Item number of pages
278-287
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.
