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:
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_tree.html
[4] http://en.wikipedia.org/wiki/Prim%27s_algorithm