Timeline for What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?
Current License: CC BY-SA 2.5
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2010 at 12:22 | comment | added | Louigi Addario-Berry | Hi Kostas! As I mentioned in the comments to the original question, the heuristic from percolation is that for $d$ large, the MST should behave like the MST of the complete graph, and hence have diameter of order $n^{1/3}$. So, although the total lengths of the TSP and the MST are asymptotically equivalent, I expect their diameters to be rather different. | |
| Sep 21, 2010 at 10:13 | history | answered | Konstantinos Panagiotou | CC BY-SA 2.5 |