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

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

Lars Hellström wrote:
> Andreas Kupries skrev:
>> Michał Antoniewski wrote:
>>> Generally, TSP is problem concerning complete graphs, but there is a 
>>> way of handling other graphs by adding edges with very big weights
>>
>> Can these big weights be 'Inf'inity ? Or do they have to be tailired 
>> to the existing weights in some way ?
> 
> One thing this would depend on is whether the route found is required to 
> be a cycle, or can visit vertices more than once. Finding a Hamiltonian 
> cycle in the complete graph is easy, finding one in a sparser graph is 
> not so easy.

 From my look at the two algorithms it seems to create a cycle where vertices 
are visited once.

>> Greedy max-matching ... Is my understanding correct that this would 
>> find a matching, but not necessarily the maximal one ? Or not the best 
>> maximal per the weights ?
> 
> Note the following fine distinction:
> 
> MaximUM matching: One that is at least as great (in e.g. size or total 
> weight) as any other matching.
> 
> MaximAL matching: One that is not a proper subset of any other matching, 
> and thus maximal w.r.t. set inclusion in the set of all matchings.
> 
> A greedy algorithm would probably return a maximal matching, with no 
> guarantee of it being maximum. (The "no guarantee" part is not so 
> surprising; checking whether a given matching is maximum is easily seen 
> to be a problem in co-NP.)

Thanks for the clarification.

Andreas.