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. Confused, Anders [1] http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/metric_tsp_approx.html [2] http://www.boost.org/doc/libs/1_46_1/libs/graph/test/metric_tsp_approx.cpp [3] http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/prim_minimum_spanning_tr... [4] http://en.wikipedia.org/wiki/Prim%27s_algorithm