On Tue, Jun 7, 2011 at 4:45 PM, Jeremiah Willcock
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
Are you using an adjacency matrix as your representation?
Yes.
Are your graphs dense?
Yes they are complete graphs, so that is as dense as it gets I guess.
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.
Right. My point is that the documentation for metric_tsp_approx and for prim_minimum_spanning_tree suggests that I should see O( E log (V) ) time complexity, which for complete graphs is O(V^2 log (V) ) when in fact I am seeing V^2 which is better. Does the BGL documentation say something about differing time complexity for adjacency_matrix and dense graphs? should it? Anders