Boost Users :
Subject: [Boost-users] BGL metric_tsp_approx time complexity?
From: Anders Wallin (anders.e.e.wallin_at_[hidden])
Date: 2011-06-07 06:29:19
I ran metric_tsp_approx on a number of TSPLIB problems and got the
This would indicate the time-complexity is V^2 (V is the number of
However the documentation  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  also lists as
O(E log V).
However I then go to  and see that for an adjacency matrix prim's
algorithm runs in V^2.
Boost-users 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