On Hard Instances of Approximate Vertex Cover
DSpace at IIT Bombay
View Archive InfoField | 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
|
|