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
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