# Question about Weighted Vertex Cover algorithm

*From*: "Gotch" <eliko778@xxxxxxxxx>*Date*: 13 Dec 2005 05:42:29 -0800

Hi,

I need to generalize the algorithm given in CLRS book for vertex cover

problem and then show that for every C>0 exists a graph with weights

(each vertex has a weight) for which this expantion of the algorithm

gives a solution C times worst than the optimal one.

I think I found a way to generalize it but it's a 2 Approximation

algorithm, so it can't have a grapsh for which the solution is C times

worst since C might be bigger than 2.

Any ideas?

Thanks,

Eliko

.

**Follow-Ups**:

- Prev by Date:
**Re: Decidability: Turing machines and languages** - Next by Date:
**Re: Question about Weighted Vertex Cover algorithm** - Previous by thread:
**Decidability: Turing machines and languages** - Next by thread:
**Re: Question about Weighted Vertex Cover algorithm** - Index(es):