{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:42:58Z","timestamp":1725486178287},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540430025"},{"type":"electronic","value":"9783540452942"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45294-x_20","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T02:45:12Z","timestamp":1181616312000},"page":"232-243","source":"Crossref","is-referenced-by-count":6,"title":["The Directed Minimum-Degree Spanning Tree Problem"],"prefix":"10.1007","author":[{"given":"Radha","family":"Krishnan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balaji","family":"Raghavachari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,11,26]]},"reference":[{"key":"20_CR1","unstructured":"A. Agrawal, P. Klein, and R. Ravi, How tough is the minimum-degree Steiner tree? A new approximate min-max equality, TR CS-91-49, Brown University, 1991."},{"key":"20_CR2","unstructured":"M. F\u00fcrer and B. Raghavachari, An NC approximation algorithm for the minimum degree spanning tree problem, In Proc. of the 28th Annual Allerton Conf. on Communication, Control and Computing, pages 274\u2013281, 1990."},{"key":"20_CR3","unstructured":"M. F\u00fcrer and B. Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree, In Proc. of 3rd ACM-SIAM Symp. on Disc. Algorithms (SODA), pages 317\u2013324, 1992."},{"key":"20_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, 17:409\u2013423, 1994.","journal-title":"J. Algorithms"},{"key":"20_CR5","doi-asserted-by":"publisher","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:355\u2013377, 1982.","journal-title":"Networks"},{"key":"20_CR6","unstructured":"D. E. Knuth, The Stanford GraphBase: a platform for combinatorial computing, Addison Wesley, 1993."},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"J. K\u00f6nemann and R. Ravi, A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees, In Proc. of 32nd annual ACM Symposium on Theory of Computing (STOC), pages 537\u2013546, 2000.","DOI":"10.1145\/335305.335371"},{"key":"20_CR8","unstructured":"E. L. Lawler, Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, New York, 1976."},{"key":"20_CR9","unstructured":"B. Raghavachari, Algorithms for finding low degree structures, In \u201cApproximation algorithms,\u201d D. Hochbaum (ed.), PWS Publishers Inc., pages 266\u2013295, 1996."},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"R. Ravi, Rapid rumor ramification: approximating the minimum broadcast time, In Proc. of 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 202\u2013213, 1994.","DOI":"10.1109\/SFCS.1994.365693"},{"key":"20_CR11","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, In Proc. of 25th Annual ACM Symp. on the Theory of Computing (STOC), pages 438\u2013447, 1993.","DOI":"10.1145\/167088.167209"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"R. Ravi, B. Raghavachari, and P. Klein, Approximation through local optimality: designing networks with small degree, In Proc. of 12th Conf. on Foundations of Software Tech. and Theoret. Comp. Sci. (FSTTCS), pages 279\u2013290. Lect. Notes in Comp. Sci. 652, 1992.","DOI":"10.1007\/3-540-56287-7_112"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF01788671","volume":"5","author":"S. Win","year":"1989","unstructured":"S. Win, On a connection between the existence of k-trees and the toughness of a graph, Graphs and Combinatorics, 5:201\u2013205, 1989.","journal-title":"Graphs and Combinatorics"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45294-X_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T01:28:02Z","timestamp":1556501282000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45294-X_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540430025","9783540452942"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-45294-x_20","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}