Record Details

On Hard Instances of Approximate Vertex Cover

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title On Hard Instances of Approximate Vertex Cover
 
Creator VISHWANATHAN, S
 
Subject algorithms
graphs
approximation algorithms
vertex cover
 
Description We show that if there is a 2 - is an element of approximation algorithm for vertex cover on graphs with vector chromatic number at most 2 + delta, then there is a 2 - f (is an element of, delta) approximation algorithm for vertex cover for all graphs.
 
Publisher ASSOC COMPUTING MACHINERY
 
Date 2011-07-18T20:51:48Z
2011-12-26T12:50:49Z
2011-12-27T05:36:57Z
2011-07-18T20:51:48Z
2011-12-26T12:50:49Z
2011-12-27T05:36:57Z
2008
 
Type Article
 
Identifier ACM TRANSACTIONS ON ALGORITHMS, 5(1), -
1549-6325
http://dx.doi.org/10.1145/1435375.1435382
http://dspace.library.iitb.ac.in/xmlui/handle/10054/5063
http://hdl.handle.net/10054/5063
 
Language en