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