{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T07:12:29Z","timestamp":1761981149775,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319096193"},{"type":"electronic","value":"9783319096209"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09620-9_9","type":"book-chapter","created":{"date-parts":[[2014,7,16]],"date-time":"2014-07-16T02:07:37Z","timestamp":1405476457000},"page":"96-107","source":"Crossref","is-referenced-by-count":4,"title":["Approximation of the Degree-Constrained Minimum Spanning Hierarchies"],"prefix":"10.1007","author":[{"given":"Mikl\u00f3s","family":"Moln\u00e1r","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Durand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Massinissa","family":"Merabet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","series-title":"LNCS","first-page":"460","volume-title":"ICALP 1979","author":"C.H. Papadimitriou","year":"1979","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract). In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol.\u00a071, pp. 460\u2013470. Springer, Heidelberg (1979)"},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/S0377-2217(99)00458-0","volume":"125","author":"D. Cieslik","year":"2000","unstructured":"Cieslik, D.: The vertex degrees of minimum spanning trees. European Journal of Operational Research\u00a0125, 278\u2013282 (2000)","journal-title":"European Journal of Operational Research"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-642-02094-0_6","volume-title":"Algorithmics of Large and Complex Networks","author":"S. Ruzika","year":"2009","unstructured":"Ruzika, S., Hamacher, H.W.: A Survey on Multiple Objective Minimum Spanning Tree Problems. In: Lerner, J., Wagner, D., Zweig, K.A. (eds.) Algorithmics. LNCS, vol.\u00a05515, pp. 104\u2013116. Springer, Heidelberg (2009)"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s00453-001-0038-2","volume":"31","author":"R. Ravi","year":"2001","unstructured":"Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica\u00a031, 58\u201378 (2001)","journal-title":"Algorithmica"},{"key":"9_CR5","unstructured":"Deo, N., Hakimi, S.: The shortest generalized Hamiltonian tree. In: Sixth Annual Allerton Conference, pp. 879\u2013888 (1968)"},{"key":"9_CR6","unstructured":"Moln\u00e1r, M.: Hierarchies to Solve Constrained Connected Spanning Problems. Technical Report 11029, LIRMM (2011)"},{"key":"9_CR7","unstructured":"Merabet, M., Durand, S., Molnar, M.: Exact solution for bounded degree connected spanning problems. Technical Report 12027, Laboratoire d\u2019Informatique de Robotique et de Micro\u00e9lectronique de Montpellier - LIRMM (2012)"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/j.osn.2005.10.001","volume":"2","author":"Y. Zhou","year":"2005","unstructured":"Zhou, Y., Poo, G.S.: Optical multicast over wavelength-routed wdm networks: A survey. Optical Switching and Networking\u00a02, 176\u2013197 (2005)","journal-title":"Optical Switching and Networking"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"1628","DOI":"10.1109\/50.908667","volume":"18","author":"M. Ali","year":"2000","unstructured":"Ali, M., Deogun, J.: Cost-effective implementation of multicasting in wavelength-routed networks. IEEE J. Lightwave Technol., Special Issue on Optical Networks\u00a018, 1628\u20131638 (2000)","journal-title":"IEEE J. Lightwave Technol., Special Issue on Optical Networks"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1093\/comjnl\/10.4.374","volume":"10","author":"A.K. Obruca","year":"1968","unstructured":"Obruca, A.K.: Spanning tree manipulation and the travelling salesman problem. The Computer Journal\u00a010, 374\u2013377 (1968)","journal-title":"The Computer Journal"},{"key":"9_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1145\/167088.167209","volume-title":"Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC 1993","author":"R. Ravi","year":"1993","unstructured":"Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Many birds with one stone: multi-objective approximation algorithms. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC 1993, pp. 438\u2013447. ACM, New York (1993)"},{"key":"9_CR13","first-page":"317","volume-title":"Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1992","author":"M. F\u00fcrer","year":"1992","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum degree spanning tree to within one from the optimal degree. In: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1992, pp. 317\u2013324. Society for Industrial and Applied Mathematics, Philadelphia (1992)"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Goemans, M.: Minimum bounded degree spanning trees. In: 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, pp. 273\u2013282 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"key":"9_CR15","first-page":"661","volume-title":"STOC 2007: Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing","author":"M. Singh","year":"2007","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: STOC 2007: Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, pp. 661\u2013670. ACM, New York (2007)"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"J.A. Hoogeveen","year":"1991","unstructured":"Hoogeveen, J.A.: Analysis of Christofides\u2019 heuristic: Some paths are more difficult than cycles. Oper. Res. Lett.\u00a010, 291\u2013295 (1991)","journal-title":"Oper. Res. Lett."}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09620-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T10:29:19Z","timestamp":1558952959000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09620-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319096193","9783319096209"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09620-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}