Boost logo

Boost Users :

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:
> 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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at