
Boost Users : 
Subject: Re: [Boostusers] BGL metric_tsp_approx time complexity?
From: Anders Wallin (anders.e.e.wallin_at_[hidden])
Date: 20110607 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 timecomplexity 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net