{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:27:10Z","timestamp":1725496030228},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770497"},{"type":"electronic","value":"9783540770503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77050-3_41","type":"book-chapter","created":{"date-parts":[[2007,11,26]],"date-time":"2007-11-26T03:39:22Z","timestamp":1196048362000},"page":"497-507","source":"Crossref","is-referenced-by-count":4,"title":["Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem"],"prefix":"10.1007","author":[{"given":"Anand","family":"Srivastav","sequence":"first","affiliation":[]},{"given":"S\u00f6ren","family":"Werth","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"41_CR1","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean TSP and other geometric problems. Journal of the ACM\u00a045(5), 754\u2013782 (1998)","journal-title":"Journal of the ACM"},{"issue":"3","key":"41_CR2","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s00453-004-1103-4","volume":"40","author":"S. Arora","year":"2004","unstructured":"Arora, S., Chang, K.: Approximation schemes for degree-restricted MST and red-blue separation problems. Algorithmica\u00a040(3), 189\u2013210 (2004)","journal-title":"Algorithmica"},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"Baltz, A., Dubhashi, D., Srivastav, A., Tansini, L., Werth, S.: Probabilistic analysis of a multidepot vehicle routing problem. In: Ramanujam, R., Sen, S. (eds.) FSTTCS 2005. LNCS, vol.\u00a03821, Springer, Heidelberg (2005), and in Random Structures and Algorithms, 30(1-2), 206\u2013225 (2007)","DOI":"10.1002\/rsa.20156"},{"key":"41_CR4","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1017\/S0305004100034095","volume":"55","author":"J. Beardwood","year":"1959","unstructured":"Beardwood, J., Halton, J.H., Hammersley, J.M.: The shortest path through many points. Proceedings of the Cambridge Philosophical Society\u00a055, 299\u2013327 (1959)","journal-title":"Proceedings of the Cambridge Philosophical Society"},{"key":"41_CR5","first-page":"11","volume-title":"Proceedings of the 19th ACM Symposium on Computational Geometry","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Euclidean bounded-degree spanning tree ratios. In: Proceedings of the 19th ACM Symposium on Computational Geometry, pp. 11\u201319. ACM Press, New York (2003)"},{"key":"41_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-540-70918-3_16","volume-title":"STACS 2007","author":"A. Dumitrescu","year":"2007","unstructured":"Dumitrescu, A., T\u00f3th, C.D.: Light orthogonal networks with constant geometric dilation. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 175\u2013187. Springer, Heidelberg (2007)"},{"key":"41_CR7","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1214\/aop\/1176996611","volume":"2","author":"J.M. Hammersley","year":"1974","unstructured":"Hammersley, J.M.: Postulates for subadditive processes. Annals of Probability\u00a02, 652\u2013680 (1974)","journal-title":"Annals of Probability"},{"key":"41_CR8","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1239\/aap\/1029955196","volume":"31","author":"K. McGivney","year":"1999","unstructured":"McGivney, K., Yukich, J.E.: Asymptotics for geometric location problems over random samples. Advances in Applied Probability\u00a031, 632\u2013642 (1999)","journal-title":"Advances in Applied Probability"},{"issue":"3","key":"41_CR9","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C. Monma","year":"1992","unstructured":"Monma, C., Suri, S.: Transitions in geometric minimum spanning trees. Discrete & Computational Geometry\u00a08(3), 265\u2013293 (1992)","journal-title":"Discrete & Computational Geometry"},{"key":"41_CR10","unstructured":"Papadimitriou, C.H.: The probabilistic analysis of matching heuristics. In: Proceedings of the 15th Allerton Conference on Communication, Control and Computing, pp. 368\u2013378 (1978)"},{"issue":"2","key":"41_CR11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"C.H. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H., Vazirani, U.V.: On two geometric problems related to the travelling salesman problem. Journal of Algorithms\u00a05(2), 231\u2013246 (1984)","journal-title":"Journal of Algorithms"},{"key":"41_CR12","unstructured":"Raghavachari, B.: Algorithms for finding low degree structures. In: Hochbaum, D. (ed.) Approximation algorithms, pp. 266\u2013295. PWS Publishers Inc. (1996)"},{"issue":"4","key":"41_CR13","doi-asserted-by":"publisher","first-page":"1057","DOI":"10.1214\/aoap\/1177004902","volume":"4","author":"C. Redmond","year":"1994","unstructured":"Redmond, C., Yukich, J.E.: Limit theorems and rates of convergence for Euclidean functionals. Annals of Applied Probability\u00a04(4), 1057\u20131073 (1994)","journal-title":"Annals of Applied Probability"},{"issue":"3","key":"41_CR14","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1214\/aoap\/1177005364","volume":"3","author":"W.T. Rhee","year":"1993","unstructured":"Rhee, W.T.: A matching problem and subadditive Euclidean functionals. Annals of Applied Probability\u00a03(3), 794\u2013801 (1993)","journal-title":"Annals of Applied Probability"},{"key":"41_CR15","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1214\/aop\/1176994411","volume":"9","author":"J.M. Steele","year":"1981","unstructured":"Steele, J.M.: Subadditive Euclidean functionals and non-linear growth in geometric probability. Annals of Probability\u00a09, 365\u2013376 (1981)","journal-title":"Annals of Probability"},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"Steele, J.M.: Probability theory and combinatorial optimization. In: CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, vol.\u00a069 (1997)","DOI":"10.1137\/1.9781611970029"},{"key":"41_CR17","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1214\/aoms\/1177700153","volume":"36","author":"V. Strassen","year":"1965","unstructured":"Strassen, V.: The existence of probability measures with given marginals. Annals of Mathematical Statistics\u00a036, 423\u2013439 (1965)","journal-title":"Annals of Mathematical Statistics"},{"key":"41_CR18","unstructured":"Weide, B.: Statistical methods in algorithm design and analysis, Ph.D. thesis, Computer Science Department, Carnegie Mellon University (1978)"},{"key":"41_CR19","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0093472","volume-title":"Probability theory of classical Euclidean optimization problems","author":"J.E. Yukich","year":"1998","unstructured":"Yukich, J.E.: Probability theory of classical Euclidean optimization problems. Lecture Notes in Mathematics, vol.\u00a01675. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77050-3_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:55:58Z","timestamp":1619506558000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77050-3_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540770497","9783540770503"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77050-3_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}