{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:39:56Z","timestamp":1725489596480},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540656913"},{"type":"electronic","value":"9783540491163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-49116-3_31","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T12:56:14Z","timestamp":1187268974000},"page":"334-344","source":"Crossref","is-referenced-by-count":1,"title":["Constructing Light Spanning Trees with Small Routing Cost"],"prefix":"10.1007","author":[{"given":"Bang Ye","family":"Wu","sequence":"first","affiliation":[]},{"given":"Kun-Mao","family":"Chao","sequence":"additional","affiliation":[]},{"given":"Chuan Yi","family":"Tang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,4,12]]},"reference":[{"issue":"1","key":"31_CR1","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"I. Alth\u00f6fer, G. Das, D. Dobkin, D. Joseph, and J. Soares, On sparse spanners of weighted graphs, Discrete and Computational Geometry, 9(1):81\u2013100, 1993.","journal-title":"Discrete and Computational Geometry"},{"key":"31_CR2","unstructured":"T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, the MIT Press, 1994."},{"issue":"3","key":"31_CR3","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. of the ACM, 34(3):596\u2013615, 1987.","journal-title":"J. of the ACM"},{"key":"31_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco, 1979."},{"issue":"3","key":"31_CR5","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1137\/0203015","volume":"3","author":"T. C. Hu","year":"1974","unstructured":"T. C. Hu, Optimum communication spanning trees, SIAM J. Computing, 3(3):188\u2013195, 1974.","journal-title":"SIAM J. Computing"},{"key":"31_CR6","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1002\/net.3230080402","volume":"8","author":"D.S. Johnson","year":"1978","unstructured":"D.S. Johnson, J.K. Lenstra, and A.H.G. Rinnooy Kan, The complexity of the network design problem, Networks, 8:279\u2013285, 1978.","journal-title":"Networks"},{"key":"31_CR7","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/BF01294129","volume":"14","author":"S. Khuller","year":"1995","unstructured":"S. Khuller, B. Raghavachari, and N. Young, Balancing minimum spanning trees and shortest-path trees, Algorithmica, 14:305\u2013321, 1995.","journal-title":"Algorithmica"},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1137\/0601008","volume":"1","author":"R. Wong","year":"1980","unstructured":"R. Wong, Worst-case analysis of network design problem heuristics. SIAM J. Algebraic Discrete Mathematics, 1:51\u201363, 1980.","journal-title":"SIAM J. Algebraic Discrete Mathematics"},{"key":"31_CR9","unstructured":"B. Y. Wu, G. Lancia, V. Bafna, K. M. Chao, R. Ravi, and C. Y. Tang, A polynomial time approximation scheme for minimum routing cost spanning trees, Proceedings of Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998), pp. 21\u201332, 1998."}],"container-title":["Lecture Notes in Computer Science","STACS 99"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49116-3_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T23:44:36Z","timestamp":1550792676000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49116-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540656913","9783540491163"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/3-540-49116-3_31","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}