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

[Lars H. <Lar...@re...>]

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.

For metric TSP (i.e., the triangle inequality holds), you're not 
allowed to exceed the weight of the shortest path between the endpoints 
anyway.

There's also the issue that the size of (number of bits needed to 
encode) the weights sometimes becomes the deciding factor for the 
complexity of graph algorithms, but that mostly figures in arguments 
that goes: Well you've constructed an example where this algorithm 
appears to have a higher complexity than we claimed it did, but that's 
just because you've used gigantic weights, and if you do your math 
carefully you'll see that the basic bitsize of your example grows much 
faster than the number of edges in it. Probably not so relevant for 
TSP, but (if I recall correctly) important for some classical max-flow 
algorithms. 8-)}

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

Lars Hellström