{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T01:27:29Z","timestamp":1791077249645,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540359043","type":"print"},{"value":"9783540359050","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_16","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T10:46:45Z","timestamp":1151491605000},"page":"169-180","source":"Crossref","is-referenced-by-count":24,"title":["Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs"],"prefix":"10.1007","author":[{"given":"R.","family":"Ravi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: What would Edmonds do? Augmenting Paths and Witnesses for degree-bounded MSTs. In: Proceedings of 8th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (2005)","DOI":"10.1007\/11538462_3"},{"key":"16_CR2","unstructured":"Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: Push Relabel and an Improved Approximation Algorithm for the Bounded-degree MST Problem. In: ICALP (2006)"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<125::AID-JGT1>3.0.CO;2-X","volume":"33","author":"M. Ellingham","year":"2000","unstructured":"Ellingham, M., Zha, X.: Toughness, trees and walks. J. Graph Theory\u00a033, 125\u2013137 (2000)","journal-title":"J. Graph Theory"},{"key":"16_CR4","unstructured":"Fischer, T.: Optimizing the degree of minimum weight spanning trees. Technical report, Department of Computer Science, Cornell University (1993)"},{"key":"16_CR5","unstructured":"Furer, M., Raghavachari, B.: Approximating the minimum degree spanning tree to within one from the optimal degree. In: SODA 1992: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 317\u2013324 (1992): Society for Industrial and Applied Mathematics"},{"key":"16_CR6","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":"16_CR7","unstructured":"Goemans, M.: Personal Communication"},{"key":"16_CR8","volume-title":"Traveling salesman problem and its variations","author":"G. Gutin","year":"2002","unstructured":"Gutin, G., Punnen, A.P.: Traveling salesman problem and its variations. Kluwer Publications, Dordrecht (2002)"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1145\/335305.335371","volume-title":"STOC 2000: Proceedings of the thirty-second annual ACM symposium on Theory of computing","author":"J. K\u00f6nemann","year":"2000","unstructured":"K\u00f6nemann, J., Ravi, R.: A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. In: STOC 2000: Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 537\u2013546. ACM Press, New York (2000)"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1145\/780542.780600","volume-title":"STOC 2003: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing","author":"J. K\u00f6nemann","year":"2003","unstructured":"K\u00f6nemann, J., Ravi, R.: Primal-dual meets local search: Approximating MST\u2019s with nonuniform degree bounds. In: STOC 2003: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 389\u2013395. ACM Press, New York (2003)"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Lam, F., Newman, A.: Traveling salesman path perfect graphs. Preprint (2006)","DOI":"10.1007\/s10107-006-0046-8"},{"key":"16_CR12","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and combinatorial optimization","author":"G.L. Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and combinatorial optimization. Wiley-Interscience, New York (1988)"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Ravi, R., Singh, M.: Delegate and Conquer: An LP-based approximation algorithm for Minimum Degree MSTs. Technical report, Tepper School of Business, Carnegie Mellon University (2006)","DOI":"10.1007\/11786986_16"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,5]],"date-time":"2024-02-05T00:11:31Z","timestamp":1707091891000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11786986_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}