Re: question about weighted vertex cover algorithm

What is "CLRS book"

Gotch wrote:
> Hi,
>
> Hey people,
>
>
> I need to generalize the algorithm given in CLRS book for vertex cover
> problem to the weighted 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 for the right graph or a different algorithm?
>
>
> Thanks,
> Eliko

.

Relevant Pages

  • Re: Problem on an nxn grid
    ... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • Re: Graph optimization
    ... represented in the form of a graph. ... I have to add up all the weights to form the ... algorithm is going to be the best for finding the shortest path ...
    (comp.programming)
  • Re: Standard graph API?
    ... I would strongly prefer not to have weights or similar attributes as ... or function or whatever passed to the graph algorithm. ... mechanism for associating arbitrary information with objects, ...
    (comp.lang.python)
  • question about weighted vertex cover algorithm
    ... I need to generalize the algorithm given in CLRS book for vertex cover ... every C>0 exists a graph with weights for ... Any ideas for the right graph or a different algorithm? ...
    (sci.math)
  • Question about Weighted Vertex Cover algorithm
    ... 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 ...
    (comp.theory)