{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T04:24:09Z","timestamp":1745987049278,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642366932"},{"type":"electronic","value":"9783642366949"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36694-9_28","type":"book-chapter","created":{"date-parts":[[2013,3,11]],"date-time":"2013-03-11T10:08:39Z","timestamp":1362996519000},"page":"324-335","source":"Crossref","is-referenced-by-count":3,"title":["Chain-Constrained Spanning Trees"],"prefix":"10.1007","author":[{"given":"Neil","family":"Olver","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Oveis Gharan, S., Saberi, A.: An O(logn \/ loglogn)-approximation algrithm for the asymmetric traveling salesman problem. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khandekar, R., K\u00f6nemann, J., Nagarajan, V., Peis, B.: On generalizations of network design problems with degree bounds. Mathematical Programming, 1\u201328 (April 2012)","DOI":"10.1007\/s10107-012-0537-8"},{"issue":"4","key":"28_CR3","doi-asserted-by":"publisher","first-page":"1413","DOI":"10.1137\/080734340","volume":"39","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree-bounded directed network design. SIAM Journal on Computing\u00a039(4), 1413\u20131431 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Bauer, F., Varma, A.: Degree-constrained multicasting in point-to-point networks. In: Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies, INFOCOM, pp. 369\u2013376 (1995)","DOI":"10.1109\/INFCOM.1995.515897"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"4489","DOI":"10.1016\/j.tcs.2009.07.029","volume":"410","author":"K. Chaudhuri","year":"2009","unstructured":"Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids. Theoretical Computer Science\u00a0410, 4489\u20134503 (2009)","journal-title":"Theoretical Computer Science"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s00453-007-9115-5","volume":"55","author":"K. Chaudhuri","year":"2009","unstructured":"Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs. Algorithmica\u00a055, 157\u2013189 (2009)","journal-title":"Algorithmica"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: Proceedings of the 51st IEEE Symposium on Foundations of Computer Science, FOCS, pp. 575\u2013584 (2010)","DOI":"10.1109\/FOCS.2010.60"},{"issue":"3","key":"28_CR8","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M. F\u00fcrer","year":"1994","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum-degree Steiner Tree to within one of optimal. Journal of Algorithms\u00a017(3), 409\u2013423 (1994)","journal-title":"Journal of Algorithms"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Minimum bounded degree spanning trees. In: Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, FOCS, pp. 273\u2013282 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K. Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner Network Problem. Combinatorica\u00a021, 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"1783","DOI":"10.1137\/S009753970036917X","volume":"31","author":"J. K\u00f6nemann","year":"2002","unstructured":"K\u00f6nemann, J., Ravi, R.: A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. SIAM Journal on Computing\u00a031, 1783\u20131793 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Ravi, R.: Primal-dual meets local search: approximating MST\u2019s with nonuniform degree bounds. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC, pp. 389\u2013395 (2003)","DOI":"10.1145\/780542.780600"},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"Oveis Gharan, S., Saberi, A.: The asymmetric traveling salesman problem on graphs with bounded genus. ArXiv (January 2011), http:\/\/arxiv.org\/abs\/0909.2849","DOI":"10.1137\/1.9781611973082.75"},{"issue":"1","key":"28_CR14","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(1), 58\u201378 (2001)","journal-title":"Algorithmica"},{"key":"28_CR15","unstructured":"Schrijver, A.: Combinatorial Optimization, Polyhedra and Efficiency. Springer (2003)"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC, pp. 661\u2013670 (2007)","DOI":"10.1145\/1250790.1250887"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"Zenklusen, R.: Matroidal degree-bounded minimum spanning trees. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1512\u20131521 (2012)","DOI":"10.1137\/1.9781611973099.120"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36694-9_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T23:54:11Z","timestamp":1745970851000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36694-9_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642366932","9783642366949"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36694-9_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}