{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:12:58Z","timestamp":1725664378242},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540613107"},{"type":"electronic","value":"9783540684534"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61310-2_9","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:28:25Z","timestamp":1330291705000},"page":"105-117","source":"Crossref","is-referenced-by-count":1,"title":["A network-flow technique for finding low-weight bounded-degree spanning trees"],"prefix":"10.1007","author":[{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monika","family":"Klemmstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balaji","family":"Raghavachari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neal","family":"Young","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"9_CR1","volume-title":"Network flows (theory, algorithms and applications)","author":"R. K. Ahuja","year":"1993","unstructured":"R. K. Ahuja, T. L. Magnanti and J. B. Orlin. Network flows (theory, algorithms and applications). Prentice Hall, Englewood Cliffs, NJ, 1993."},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/BF01589417","volume":"42","author":"C. Brezovec","year":"1988","unstructured":"C. Brezovec, G. Cornu\u00e9jols, F. Glover. A matroid algorithm and its application to the efficient solution of two optimization problems in graphs. Math. Programming\n42 (1988), pp. 471\u2013487.","journal-title":"Math. Programming"},{"key":"9_CR3","unstructured":"T. Fischer. Optimizing the degree of minimum weight spanning trees. Tech. Rep. 93-1338, Dept. of Computer Science, Cornell University, April 1993."},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M. F\u00fcrer","year":"1994","unstructured":"M. F\u00fcrer and B. Raghavachari. Approximating the minimum-degree Steiner tree to within one of optimal. J. Algorithms\n17 (1994), pp. 409\u2013423.","journal-title":"J. Algorithms"},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/net.3230080304","volume":"8","author":"H. N. Gabow","year":"1978","unstructured":"H. N. Gabow. A good algorithm for smallest spanning trees with a degree constraint. Networks 8 (1978), pp. 201\u2013208.","journal-title":"Networks"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0196-6774(84)90042-7","volume":"5","author":"H. N. Gabow","year":"1984","unstructured":"H. N. Gabow and R. E. Tarjan. Efficient algorithms for a family of matroid intersection problems. J. Algorithms 5 (1984), pp. 80\u2013131.","journal-title":"J. Algorithms"},{"key":"9_CR7","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. Freeman, San Francisco, CA, 1979."},{"key":"9_CR8","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1002\/net.3230120402","volume":"12","author":"B. Gavish","year":"1982","unstructured":"B. Gavish. Topological design of centralized computer networks \u2014 formulations and algorithms. Networks 12 (1982), pp. 355\u2013377.","journal-title":"Networks"},{"key":"9_CR9","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/978-94-011-7557-9_10","volume-title":"Combinatorial Programming: Methods and Applications","author":"F. Glover","year":"1975","unstructured":"F. Glover, D. Klingman. Finding minimum spanning trees with a fixed number of links at anode. In: B. Roy (ed.), Combinatorial Programming: Methods and Applications. D. Reidel Publishing Company, Dordrecht-Holland, 1975. pp. 191\u2013201."},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"S. Khuller, B. Raghavachari and N. Young. Low degree spanning trees of small weight. Proc. of 26th Annual ACM Symp. on the Theory of Computing, pp. 412\u2013421, May 1994. To appear in SIAM J. Comput.","DOI":"10.1145\/195058.195212"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/BF01294129","volume":"14","author":"S. Khuller","year":"1995","unstructured":"S. Khuller, B. Raghavachari, N. Young, Balancing minimum spanning trees and shortest-path trees. Algorithmica\n14 (1995), pp. 305\u2013321.","journal-title":"Algorithmica"},{"key":"9_CR12","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1287\/opre.37.4.531","volume":"37","author":"C. L. Monma","year":"1989","unstructured":"C. L. Monma, D. Shallcross. Methods for designing communication networks with certain two-connected survivability constraints. Oper. Res. 37 (1989), pp. 531\u2013541.","journal-title":"Oper. Res."},{"key":"9_CR13","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C. L. Monma","year":"1992","unstructured":"C. L. Monma, S. Suri, Transitions in geometric minimum spanning trees. Discrete & Computational Geometry 8 (1992), pp. 265\u2013293.","journal-title":"Discrete & Computational Geometry"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0305-0548(80)90022-2","volume":"7","author":"S. C. Narula","year":"1980","unstructured":"S. C. Narula and C. A. Ho. Degree-constrained minimum spanning tree. Comput. Ops. Res.\n7 (1980), pp. 239\u2013249.","journal-title":"Comput. Ops. Res."},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"C. H. Papadimitriou","year":"1984","unstructured":"C. H. Papadimitriou, U. V. Vazirani, On two geometric problems related to the traveling salesman problem. J. Algorithms 5 (1984), pp. 231\u2013246.","journal-title":"J. Algorithms"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and H. B. Hunt III. Many birds with one stone: multi-objective approximation algorithms. Manuscript. A preliminary version appeared in Proc. 25th Annual ACM Symp. on the Theory of Computing, pp. 438\u2013447, May 1993.","DOI":"10.1145\/167088.167209"},{"key":"9_CR17","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02570700","volume":"14","author":"G. Robins","year":"1995","unstructured":"G. Robins and J. S. Salowe. Low-degree minimum spanning trees. Discrete and Computational Geometry 14 (1995), pp. 151\u2013166.","journal-title":"Discrete and Computational Geometry"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0166-218X(94)90133-3","volume":"54","author":"J. S. Salowe","year":"1994","unstructured":"J. S. Salowe. Euclidean spanner graphs with degree four. Discrete Appl. Math. 54 (1994), pp. 55\u201366.","journal-title":"Discrete Appl. Math."},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/0305-0548(85)90032-2","volume":"12","author":"M. Savelsbergh","year":"1985","unstructured":"M. Savelsbergh and A. Volgenant. Edge exchanges in the degree-constrained minimum spanning tree problem. Comput. Ops. Res.\n12 (1985), pp. 341\u2013348.","journal-title":"Comput. Ops. Res."},{"key":"9_CR20","volume-title":"Lecture Notes on Mathematics # 1531","author":"M. Stoer","year":"1992","unstructured":"M. Stoer. Design of survivable networks. Lecture Notes on Mathematics # 1531. Springer, Heidelberg, 1992."},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0377-2217(89)90169-0","volume":"39","author":"A. Volgenant","year":"1989","unstructured":"A. Volgenant. A Lagrangean approach to the degree-constrained minimum spanning tree problem. Europ. J. Ops. Res.\n39 (1989), pp. 325\u2013331.","journal-title":"Europ. J. Ops. Res."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61310-2_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:30:56Z","timestamp":1619573456000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61310-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540613107","9783540684534"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-61310-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}