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

[Michał A. <ant...@gm...>]

>>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.

>>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 -
Approximation Algorithms. 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 ).

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


Best Regards,
Michał Antoniewski