The minimal spanning tree and the upper box dimension
HTML articles powered by AMS MathViewer
- by Gady Kozma, Zvi Lotker and Gideon Stupp PDF
- Proc. Amer. Math. Soc. 134 (2006), 1183-1187 Request permission
Abstract:
We show that the $\alpha$-weight of an MST over $n$ points in a metric space with upper box dimension $d$ has a bound independent of $n$ if $\alpha >d$ and does not have one if $\alpha <d$.References
- Michael Aizenman, Almut Burchard, Charles M. Newman, and David B. Wilson, Scaling limits for minimal and random spanning trees in two dimensions, Random Structures Algorithms 15 (1999), no.Β 3-4, 319β367. Statistical physics methods in discrete probability, combinatorics, and theoretical computer science (Princeton, NJ, 1997). MR 1716768, DOI 10.1002/(SICI)1098-2418(199910/12)15:3/4<319::AID-RSA8>3.3.CO;2-7
- David Aldous and J. Michael Steele, The objective method: probabilistic combinatorical optimization and local weak convergence, Probability on discrete structures, 1β72, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. http://stat-www.berkeley.edu/users/aldous/me101.ps.Z
- Kenneth S. Alexander, The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees, Ann. Appl. Probab. 6 (1996), no.Β 2, 466β494. MR 1398054, DOI 10.1214/aoap/1034968140
- Thomas H. Corman, Charles E. Leiserson and Ronald L. Rivest, Introduction to algorithms, MIT Press, 1991.
- L. Fejes, Γber einen geometrischen Satz, Math. Z. 46 (1940), 83β85 (German). MR 1587, DOI 10.1007/BF01181430
- L. Few, The shortest path and the shortest road through $n$ points, Mathematika 2 (1955), 141β144. MR 78715, DOI 10.1112/S0025579300000784
- Kenneth Falconer, Fractal geometry, John Wiley & Sons, Ltd., Chichester, 1990. Mathematical foundations and applications. MR 1102677
- E. N. Gilbert and H. O. Pollak, Steiner minimal trees, SIAM J. Appl. Math. 16 (1968), 1β29. MR 223269, DOI 10.1137/0116001
- Sungchul Lee, Worst case asymptotics of power-weighted Euclidean functionals, Discrete Math. 256 (2002), no.Β 1-2, 291β300. MR 1927073, DOI 10.1016/S0012-365X(01)00437-X
- Shlomo Moran, On the length of optimal TSP circuits in sets of bounded diameter, J. Combin. Theory Ser. B 37 (1984), no.Β 2, 113β141. MR 766629, DOI 10.1016/0095-8956(84)90067-4
- T. L. Snyder and J. Michael Steele, Worst case growth rates for minimal and greedy matchings with power weighted edges, Technical report, Princeton University, Program in Operations Research and Statistics (1987).
- J. Michael Steele, Probabilistic and worst case analyses of classical problems of combinatorial optimization in Euclidean space, Math. Oper. Res. 15 (1990), no.Β 4, 749β770. MR 1080476, DOI 10.1287/moor.15.4.749
- S. Verblunsky, On the shortest path through a number of points, Proc. Amer. Math. Soc. 2 (1951), 904β913. MR 45403, DOI 10.1090/S0002-9939-1951-0045403-1
- J. E. Yukich, Worst case asymptotics for some classical optimization problems, Combinatorica 16 (1996), no.Β 4, 575β586. MR 1433644, DOI 10.1007/BF01271275
Additional Information
- Gady Kozma
- Affiliation: Institute for Advanced Study, 1 Einstein Drive, Princeton, New Jersey 08540
- MR Author ID: 321409
- Email: gady@ias.edu
- Zvi Lotker
- Affiliation: Office Centrum voor Wiskunde en Informatica, Kruislaan, 413, NL-1098 SJ Amsterdam, The Netherlands
- Email: zvilo@eng.tau.ac.il
- Gideon Stupp
- Affiliation: MIT Computer Science and Artificial Intelligence Laboratory, The Stata Center, 32 Vassar Street, Cambridge, Massachusetts 02139
- Email: gstupp@theory.csail.mit.edu
- Received by editor(s): January 7, 2004
- Received by editor(s) in revised form: October 25, 2004
- Published electronically: September 20, 2005
- Communicated by: John R. Stembridge
- © Copyright 2005 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 134 (2006), 1183-1187
- MSC (2000): Primary 68U05, 05C05
- DOI: https://doi.org/10.1090/S0002-9939-05-08061-5
- MathSciNet review: 2196055