{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:57:20Z","timestamp":1725663440112},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540562870"},{"type":"electronic","value":"9783540475071"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56287-7_112","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:02:07Z","timestamp":1330254127000},"page":"279-290","source":"Crossref","is-referenced-by-count":8,"title":["Approximation through local optimality: Designing networks with small degree"],"prefix":"10.1007","author":[{"given":"R.","family":"Ravi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B.","family":"Raghavachari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"A. Agrawal, P. Klein and R. Ravi, \u201cWhen trees collide: an approximation algorithm for the generalized Steiner tree problem on networks,\u201d Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (1991), pp. 134\u2013144.","DOI":"10.1145\/103418.103437"},{"key":"21_CR2","unstructured":"A. Agrawal, P. Klein and R. Ravi, \u201cHow tough is the minimum-degree Steiner tree? An approximate min-max equality (complete with algorithms)\u201d, TR-CS-91-49, Brown University (1991), Submitted to SIAM J. on Disc. Math."},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0166-218X(90)90001-S","volume":"28","author":"D. Bauer","year":"1990","unstructured":"D. Bauer, S.L. Hakimi, and E. Schmeichel, \u201cRecognizing tough graphs is NP-hard,\u201d Disc. Appl. Math. 28 (1990), pp. 191\u2013195.","journal-title":"Disc. Appl. Math."},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0012-365X(73)90138-6","volume":"5","author":"V. Chv\u00e1tal","year":"1973","unstructured":"V. Chv\u00e1tal, \u201cTough graphs and Hamiltonian circuits,\u201d Disc. Math. 5 (1973), pp. 215\u2013228.","journal-title":"Disc. Math."},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J. Edmonds","year":"1973","unstructured":"J. Edmonds, and E. L. Johnson, \u201cMatching, Euler tours and the Chinese postman\u201d, Math. Prog. 5, (1973), pp. 88\u2013124.","journal-title":"Math. Prog."},{"key":"21_CR6","unstructured":"M. F\u00fcrer and B. Raghavachari, \u201cAn NC approximation algorithm for the minimum-degree spanning tree problem,\u201d Proceedings of the 28th Annual Allerton Conference on Communication, Control and Computing (1990), pp. 274\u2013281."},{"key":"21_CR7","unstructured":"M. F\u00fcrer and B. Raghavachari, \u201cApproximating the minimum-degree spanning tree to within one from the optimal degree\u201d, Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (1992), pp. 317\u2013324."},{"key":"21_CR8","unstructured":"M. F\u00fcrer and B. Raghavachari, \u201cApproximating the minimum-degree spanning and Steiner trees to within one from the optimal degree\u201d, TR CS-92-13, Pennsylvania State University, June 1992."},{"key":"21_CR9","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, San Francisco (1979)."},{"key":"21_CR10","unstructured":"M. X. Goemans, and D. P. Williamson, \u201cA general approximation technique for constrained forest problems\u201d, Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (1992), pp. 307\u2013316."},{"key":"21_CR11","unstructured":"P. Klein and R. Ravi, \u201cApproximation through uncrossing: From edge-cuts to node-cuts,\u201d submitted to the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms."},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"G. L. Nemhauser, and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley Interscience series in Disc. Math. and Optimization (1988).","DOI":"10.1002\/9781118627372"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56287-7_112.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:03:14Z","timestamp":1605646994000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56287-7_112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540562870","9783540475071"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-56287-7_112","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}