Re: [Boost-users] BGL metric_tsp_approx time complexity?

On Tue, 7 Jun 2011, Anders Wallin wrote:

On Tue, Jun 7, 2011 at 4:45 PM, Jeremiah Willcock wrote:

...

On Tue, 7 Jun 2011, Anders Wallin wrote:

...

Hi all,

I ran metric_tsp_approx on a number of TSPLIB problems and got the following graph: http://goo.gl/iGYsH

This would indicate the time-complexity is V^2

Are you using an adjacency matrix as your representation?

Yes.

...

 Are your graphs dense?

Yes they are complete graphs, so that is as dense as it gets I guess.

...

I don't remember what TSPLIB contains exactly -- are you using Euclidean problems that would turn into dense graphs? In that case, just reading the graph's distance matrix would take O(V^2), and so the complexity you are seeing is correct.

Right. My point is that the documentation for metric_tsp_approx and for prim_minimum_spanning_tree suggests that I should see O( E log (V) ) time complexity, which for complete graphs is O(V^2 log (V) ) when in fact I am seeing V^2 which is better. Does the BGL documentation say something about differing time complexity for adjacency_matrix and dense graphs? should it?

I do not believe the code uses any special-case algorithms for dense graphs and uses a d-ary heap, so it probably actually is O(V^2 log_4 V); you might not be hitting a large enough V to see the log term. It is odd that the times follow the V^2 line so closely, though. Try changing the 4 on line 323 of to 2 and see if that does anything to your times. -- Jeremiah Willcock