Boost logo

Boost Users :

Subject: Re: [Boost-users] BGL metric_tsp_approx time complexity?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-06-07 14:27:49

On Tue, 7 Jun 2011, Anders Wallin wrote:

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

I do not believe the code uses any special-case algorithms for dense
graphs and uses a d-ary heap, so it probably actually is O(V^2 log_4 V);
you might not be hitting a large enough V to see the log term. It is odd
that the times follow the V^2 line so closely, though. Try changing the 4
on line 323 of <boost/graph/dijkstra_shortest_paths.hpp> to 2 and see if
that does anything to your times.

-- Jeremiah Willcock

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at