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

Subject: Re: [Boost-users] BGL metric_tsp_approx time complexity?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-06-07 09:45:00

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 (V is the number of
> cities/vertices).
> However the documentation [1] says O(E log V).
> A complete graph has O(V^2) edges, so the documentation would indicate
> metric_tsp_approx is O( V^2 log V )  (?)
>
> The heavy lifting in metric_tsp_approx is done by
> prim_minimum_spanning_tree, which the documentation [3] also lists as
> O(E log V).
> However I then go to [4] and see that for an adjacency matrix prim's
> algorithm runs in V^2.

Are you using an adjacency matrix as your representation?  Are your graphs 
dense?  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.

-- Jeremiah Willcock