{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T10:42:41Z","timestamp":1784544161537,"version":"3.55.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2012,1]]},"DOI":"10.1007\/s00493-012-2552-z","type":"journal-article","created":{"date-parts":[[2012,2,10]],"date-time":"2012-02-10T02:41:55Z","timestamp":1328841715000},"page":"1-33","source":"Crossref","is-referenced-by-count":15,"title":["A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks"],"prefix":"10.1007","volume":"32","author":[{"given":"Omer","family":"Angel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abraham D.","family":"Flaxman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David B.","family":"Wilson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,2,10]]},"reference":[{"issue":"1","key":"2552_CR1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1214\/aoap\/1177005773","volume":"2","author":"Florin AvramDimitris Bertsimas","year":"1992","unstructured":"Florin Avram and Dimitris Bertsimas: The minimum spanning tree constant in geometrical probability and under the independent model: a unified approach, Ann. Appl. Probab. 2(1) (1992), 113\u2013130.","journal-title":"Ann. Appl. Probab."},{"issue":"3","key":"2552_CR2","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/rsa.20241","volume":"35","author":"L. Addario-Berry","year":"2009","unstructured":"L. Addario-Berry, N. Broutin and B. Reed: Critical random graphs and the structure of a minimum spanning tree, Random Structures Algorithms 35(3) (2009), 323\u2013347.","journal-title":"Random Structures Algorithms"},{"key":"2552_CR3","first-page":"261","volume":"5","author":"N. R. Achuthan","year":"1992","unstructured":"N. R. Achuthan and L. Caccetta: Minimum weight spanning trees with bounded diameter, Australas. J. Combin. 5 (1992), 261\u2013276.","journal-title":"Australas. J. Combin."},{"key":"2552_CR4","first-page":"279","volume":"8","author":"N. R. Achuthan","year":"1993","unstructured":"N. R. Achuthan and L. Caccetta: Addendum: \u201cMinimum weight spanning trees with bounded diameter\u201d, Australas. J. Combin. 8 (1993), 279\u2013281.","journal-title":"Australas. J. Combin."},{"issue":"6","key":"2552_CR5","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1080\/00207160211289","volume":"79","author":"A. Abdalla","year":"2002","unstructured":"Ayman Abdalla and Narsingh Deo: Random-tree diameter and the diameterconstrained MST, Int. J. Comput. Math. 79(6) (2002), 651\u2013663.","journal-title":"Int. J. Comput. Math."},{"key":"2552_CR6","first-page":"97","volume":"136","author":"A. Abdalla","year":"1999","unstructured":"A. Abdalla, N. Deo and R. Franceschini: Parallel heuristics for the diameterconstrained MST problem, in: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), volume 136, 97\u2013118, 1999.","journal-title":"Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999)"},{"issue":"2","key":"2552_CR7","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.orl.2004.05.005","volume":"33","author":"E. Althaus","year":"2005","unstructured":"Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Knemann, Edgar A. Ramos and Martin Skutella: Approximating k-hop minimumspanning trees, Oper. Res. Lett. 33(2) (2005), 115\u2013120.","journal-title":"Oper. Res. Lett."},{"issue":"20","key":"2552_CR8","doi-asserted-by":"crossref","first-page":"11211","DOI":"10.1073\/pnas.1635191100","volume":"100","author":"D. Aldous","year":"2003","unstructured":"David Aldous and Allon G. Percus: Scaling and universality in continuous length combinatorial optimization, Proc. Natl. Acad. Sci. USA 100(20) (2003), 11211\u201311215 (electronic).","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"3","key":"2552_CR9","doi-asserted-by":"crossref","first-page":"037208","DOI":"10.1103\/PhysRevLett.101.037208","volume":"101","author":"M. Bayati","year":"2008","unstructured":"M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour and R. Zecchina: Statistical mechanics of Steiner trees, Physical Review Letters 101(3) (2008), 037208.","journal-title":"Physical Review Letters"},{"issue":"2","key":"2552_CR10","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s00493-004-0013-z","volume":"24","author":"B. Bollobs","year":"2004","unstructured":"Bla Bollobs, David Gamarnik, Oliver Riordan and Benny Sudakov: On the value of a random minimum weight Steiner tree, Combinatorica 24(2) (2004), 187\u2013207.","journal-title":"Combinatorica"},{"issue":"1\u20132","key":"2552_CR11","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0304-3975(99)00130-9","volume":"250","author":"J. Bar-Ilan","year":"2001","unstructured":"Judit Bar-Ilan, Guy Kortsarz and David Peleg: Generalized submodular cover problems and applications, Theoret. Comput. Sci. 250(1\u20132) (2001), 179\u2013200.","journal-title":"Theoret. Comput. Sci."},{"key":"2552_CR12","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ejor.2007.06.012","volume":"19061","author":"A. M. Costa","year":"2008","unstructured":"Alysson M. Costa, Jean-Franois Cordeauc and Gilbert Laporte: Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints, European Journal of Operational Research 1906(1) (2008), 68\u201378.","journal-title":"European Journal of Operational Research"},{"key":"2552_CR13","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1002\/net.20274","volume":"53","author":"A. M. Costa","year":"2009","unstructured":"Alysson M. Costa, Jean-Franois Cordeau and Gilbert Laporte: Models and branch-and-cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, Networks 53 (2009), 141\u2013159.","journal-title":"Networks"},{"issue":"2\u20133","key":"2552_CR14","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/j.tcs.2007.04.039","volume":"384","author":"A. E. F. Clementi","year":"2007","unstructured":"Andrea E. F. Clementi, Miriam Di Ianni, Massimo Lauria, Angelo Monti, Gianluca Rossi and Riccardo Silvestri: On the bounded-hop MST problem on random Euclidean instances, Theor. Comput. Sci. 384(2\u20133) (2007), 161\u2013167.","journal-title":"Theor. Comput. Sci."},{"key":"2552_CR15","doi-asserted-by":"crossref","unstructured":"Geir Dahl, Luis Gouveia and Cristina Requejo: On formulations and methods for the hop-constrained minimum spanning tree problem, in: Mauricio G. C. Resende and Panos M. Pardalos, editors, Handbook of Optimization in Telecommunications, 493\u2013516, 2006.","DOI":"10.1007\/978-0-387-30165-5_19"},{"issue":"4","key":"2552_CR16","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF02125348","volume":"9","author":"A. M. Frieze","year":"1989","unstructured":"A. M. Frieze and C. J. H. McDiarmid: On random minimum length spanning trees, Combinatorica 9(4) (1989), 363\u2013374.","journal-title":"Combinatorica"},{"issue":"1","key":"2552_CR17","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0166-218X(85)90058-7","volume":"10","author":"A. M. Frieze","year":"1985","unstructured":"A. M. Frieze: On the value of a random minimum spanning tree problem, Discrete Appl. Math. 10(1) (1985), 47\u201356.","journal-title":"Discrete Appl. Math."},{"key":"2552_CR18","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"Michael R. Garey and David S. Johnson: Computers and Intractability: A guide to the theory of NP-completeness, W. H. Freeman and Co., San Francisco, Calif., 1979."},{"issue":"3","key":"2552_CR19","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.10069","volume":"41","author":"L. Gouveia","year":"2003","unstructured":"Luis Gouveia and Thomas L. Magnanti: Network flow models for designing diameter-constrained minimum-spanning and Steiner trees, Networks 41(3) (2003), 159\u2013173.","journal-title":"Networks"},{"issue":"9","key":"2552_CR20","doi-asserted-by":"crossref","first-page":"959","DOI":"10.1016\/0305-0548(94)00074-I","volume":"22","author":"L. Gouveia","year":"1995","unstructured":"Luis Gouveia: Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop constraints, Computers & OR 22(9) (1995), 959\u2013970.","journal-title":"Computers & OR"},{"key":"2552_CR21","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/0377-2217(95)00090-9","volume":"95","author":"L. Gouveia","year":"1996","unstructured":"L. Gouveia: Multicommodity flow models for spanning trees with hop constraints. European Journal of Operational Research 95, 178\u2013190, 22 November 1996.","journal-title":"European Journal of Operational Research"},{"key":"2552_CR22","unstructured":"M. Gruber and G. R. Raidl: A new 0\u20131 ILP approach for the bounded diameter minimum spanning tree problem, in: 2nd Int. Network Optimization Conference, vol. 1, 178\u2013185, 2005."},{"key":"2552_CR23","unstructured":"M. Gruber and G. R. Raidl: Variable neighborhood search for the bounded diameter minimum spanning tree problem, in: Proc. of the 18th Mini Euro Conference on Variable Neighborhood Search, Tenerife, Spain, 2005."},{"key":"2552_CR24","doi-asserted-by":"crossref","unstructured":"M. Gruber, J. van Hemert and G. R. Raidl: Neighborhood searches for the bounded diameter minimum spanning tree problem embedded in a VNS, EA, and ACO, in: Proc. of the Genetic and Evolutionary Computation Conference, Seattle, volume 2. ACM Press, 2006.","DOI":"10.1145\/1143997.1144185"},{"issue":"4","key":"2552_CR25","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1002\/rsa.3240070406","volume":"7","author":"S. Janson","year":"1995","unstructured":"Svante Janson: The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph, Random Structures Algorithms 7(4) (1995), 337\u2013355.","journal-title":"Random Structures Algorithms"},{"issue":"4","key":"2552_CR26","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1017\/S0963548399003892","volume":"8","author":"S. Janson","year":"1999","unstructured":"Svante Janson: One, two and three times logn\/n for paths in a complete graph with random weights, Combin. Probab. Comput. 8(4) (1999), 347\u2013361. Random graphs and combinatorial structures (Oberwolfach, 1997).","journal-title":"Combin. Probab. Comput."},{"key":"2552_CR27","unstructured":"B. A. Julstrom and G. R. Raidl: A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem, in: 2003 GECCO Workshops Proc., Workshop on Analysis and Design of Representations (ADoRO), Chicago, 2\u20137, 2003."},{"key":"2552_CR28","doi-asserted-by":"crossref","unstructured":"Svante Janson and Johan Wstlund: Addendum to: \u201cThe minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph\u201d Structures Algorithms 7 (1995), no. 4, Janson, Random Structures Algorithms 28(4) (2006), 511\u2013512.","DOI":"10.1002\/rsa.20122"},{"key":"2552_CR29","unstructured":"Boris Kopinitsch: An ant colony optimisation algorithm for the bounded diameter minimum spanning tree problem, Master\u2019s thesis, Vienna University of Technology, Institute of Computer Graphics and Algorithms, 2006, supervised by G. Raidl and M. Gruber."},{"issue":"2\u20133","key":"2552_CR30","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/S0166-218X(99)00111-0","volume":"93","author":"G. Kortsarz","year":"1999","unstructured":"Guy Kortsarz and David Peleg: Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93(2\u20133) (1999), 265\u2013285.","journal-title":"Discrete Appl. Math."},{"key":"2552_CR31","series-title":"London Math. Soc. Lecture Note Ser.","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1017\/CBO9781107359949.008","volume-title":"Surveys in combinatorics, 1989 (Norwich, 1989)","author":"C. McDiarmid","year":"1989","unstructured":"Colin McDiarmid: On the method of bounded differences, in: Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc. Lecture Note Ser., 148\u2013188. Cambridge Univ. Press, Cambridge, 1989."},{"issue":"4","key":"2552_CR32","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0020-0190(01)00160-0","volume":"80","author":"J. Monnot","year":"2001","unstructured":"Jrme Monnot: The maximum f-depth spanning tree problem, Inform. Process. Lett. 80(4) (2001), 179\u2013187.","journal-title":"Inform. Process. Lett."},{"key":"2552_CR33","series-title":"Oxford Studies in Probability","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001","volume-title":"Random Geometric Graphs","author":"M. Penrose","year":"2003","unstructured":"Mathew Penrose: Random Geometric Graphs, volume 5 of Oxford Studies in Probability, Oxford University Press, Oxford, 2003."},{"key":"2552_CR34","unstructured":"Peter Putz: Subgradient optimization based lagrangian relaxation and relax-andcut approaches for the bounded diameter minimum spanning tree problem, Master\u2019s thesis, Vienna University of Technology, Institute of Computer Graphics and Algorithms, 2007, supervised by G. Raidl."},{"key":"2552_CR35","doi-asserted-by":"crossref","unstructured":"G\u00fcnther R. Raidl and Bryant A. Julstrom: Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem, in: SAC\u2019 03: Proc. of the 2003 ACM Symposium on Applied Computing, Melbourne, FL, 747\u2013752, 2003.","DOI":"10.1145\/952532.952678"},{"key":"2552_CR36","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1017\/S1446788700004432","volume":"7","author":"A. Rnyi","year":"1967","unstructured":"A. Rnyi and G. Szekeres: On the height of trees, J. Austral. Math. Soc. 7 (1967), 497\u2013507.","journal-title":"J. Austral. Math. Soc."},{"issue":"1","key":"2552_CR37","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0166-218X(87)90047-3","volume":"18","author":"J. Michael Steele","year":"1987","unstructured":"J. Michael Steele: On Frieze\u2019s \u03b6(3) limit for lengths of minimal spanning trees, Discrete Appl. Math. 18(1) (1987), 99\u2013103.","journal-title":"Discrete Appl. Math."},{"key":"2552_CR38","series-title":"Lecture Notes in Math.","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/BFb0071532","volume-title":"Combinatorial mathematics, X (Adelaide, 1982)","author":"G. Szekeres","year":"1983","unstructured":"G. Szekeres: Distribution of labelled trees by diameter, in: Combinatorial mathematics, X (Adelaide, 1982), volume 1036 of Lecture Notes in Math., 392\u2013397. Springer, Berlin, 1983."},{"key":"2552_CR39","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1023\/A:1018967121276","volume":"86","author":"S. Vo","year":"1999","unstructured":"Stefan Vo: The Steiner tree problem with hop constraints, Ann. Oper. Res. 86 (1999), 321\u2013345. Advances in combinatorial optimization (London, 1996).","journal-title":"Ann. Oper. Res."},{"key":"2552_CR40","unstructured":"Ferdinand Zaubzer: Lagrangian relax-and-cut and hybrid methods for the bounded diameter and the hop constrained minimum spanning tree problems, Master\u2019s thesis, Vienna University of Technology, Institute of Computer Graphics and Algorithms, 2008, supervised by G. Raidl and M. Gruber."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-012-2552-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-012-2552-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-012-2552-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T12:15:42Z","timestamp":1561292142000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-012-2552-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["2552"],"URL":"https:\/\/doi.org\/10.1007\/s00493-012-2552-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}