Ramsey numbers and an approximation algorithm for the vertex cover problem |
| |
Authors: | Burkhard Monien Ewald Speckenmeyer |
| |
Affiliation: | (1) Fachbereich 17, Theoretische Informatik, Universität Paderborn, Postfach 1621, D-4790 Paderborn, Federal Republic of Germany |
| |
Abstract: | Summary We show two results. First we derive an upper bound for the special Ramsey numbers r
k(q) where r
k(q) is the largest number of nodes a graph without odd cycles of length bounded by 2k+1 and without an independent set of size q+1 can have. We prove
The proof is constructive and yields an algorithm for computing an independent set of that size. Using this algorithm we secondly describe an O(¦V¦·¦E¦) time bounded approximation algorithm for the vertex cover problem, whose worst case ratio is
, for all graphs with at most (2k+3)
k
(2k+2) nodes (e.g. 1.8, if ¦V¦146000). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|