Re: [Boost-users] BGL metric_tsp_approx time complexity?

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

On Tue, Jun 7, 2011 at 4:45 PM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
> 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