
Boost Users : 
Subject: Re: [Boostusers] BGL metric_tsp_approx time complexity?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20110607 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 timecomplexity 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net