Boost logo

Boost Users :

Subject: [Boost-users] BGL metric_tsp_approx time complexity?
From: Anders Wallin (anders.e.e.wallin_at_[hidden])
Date: 2011-06-07 06:29:19

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



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