Re: [Tcllib-devel] ping gsoc graph work ...

[Andreas K. <and...@ac...>]

Michał Antoniewski wrote:
>  >>A graph with a Hamilton cycle is said to be /Hamiltonian/, so I 
> suppose the term you were looking for here is "non->>Hamiltonian".
>  
> That's right. Thanks.
>  
>  >>You've got maximum and maximal the wrong way round here. Finding one 
> maximal (w.r.t set inclusion) independent set is >>easy (add vertices 
> until you've covered the graph). Finding one that achieves the maximum 
> cardinality is hard.
>  
> Oh, I've mistaken the endings...AL with UM...sorry for confusion.

Well, we are here to help :)

>  >>Lars Hellström wrote:
>  >>You've got maximum and maximal the wrong way round here. Finding one 
> maximal (w.r.t set inclusion) independent set is >>easy (add vertices 
> until you've covered the graph). Finding one that achieves the maximum 
> cardinality is hard.
>  
>  >>Yes. I just googled for
>  >> weighted metric k-center
>  >>and found the PDF
>  >>http://www.corelab.ntua.gr/courses/approx-alg/material/k-center.pdf
>  >>which seems to be the basis of Michal description, it is very similar.
>  >>And it also describes it as finding maximal, not maximum, the latter 
> being NP-hard.
>  
> Actually, my main source is great book written by Vijay V. Vazirani - 

Googling... http://www.cc.gatech.edu/~vazirani/

Him I guess.

> Approximation Algorithms.

Yes, the book is listed on the page

 > That pdf is indeed very similar to what I've
> written, I think it's possible it was based on the book I mentioned ( 
> all naming, as far I can see, is the same ).

That is possible. The higher url http://www.corelab.ntua.gr/courses/approx-alg/
is unfortunately all greek to me (literally). I.e. if he is referencing the 
book as source, I can't find it, and the pdf doesn't list references



> I think, except that confusion with accidentally replacing the endings, 
> the rest of description was allright.

Yes, I thought so too, especially after reading the k-center.pdf slides.

Andreas.