{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:27:30Z","timestamp":1725460050181},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642380150"},{"type":"electronic","value":"9783642380167"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38016-7_4","type":"book-chapter","created":{"date-parts":[[2013,4,30]],"date-time":"2013-04-30T17:58:58Z","timestamp":1367344738000},"page":"30-41","source":"Crossref","is-referenced-by-count":1,"title":["Approximating Spanning Trees with Few Branches"],"prefix":"10.1007","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Bhatia, R., Khuller, S., Pless, R., Sussmann, Y.J.: The full degree spanning tree problem. In: Proc. of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 864\u2013865 (1999)"},{"issue":"3","key":"4_CR2","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s10589-007-9120-2","volume":"42","author":"R. Cerulli","year":"2009","unstructured":"Cerulli, R., Gentili, M., Iossa, A.: Bounded-degree spanning tree problems: models and new algorithms. Computational Optimization and Applications\u00a042(3), 353\u2013370 (2009)","journal-title":"Computational Optimization and Applications"},{"key":"4_CR3","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum degree spanning tree to within one from the optimal degree. In: Proc. of the Third Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA 1992), pp. 317\u2013324 (1992)"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1007\/3-540-45061-0_63","volume-title":"Automata, Languages and Programming","author":"L. Gargano","year":"2003","unstructured":"Gargano, L., Hammar, M.: There are spanning spiders in dense graphs (and we know how to find them). In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 802\u2013816. Springer, Heidelberg (2003)"},{"issue":"1-3","key":"4_CR5","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.disc.2004.04.005","volume":"285","author":"L. Gargano","year":"2004","unstructured":"Gargano, L., Hammar, M., Hell, P., Stacho, L., Vaccaro, U.: Spanning spiders and light-splitting switches. Discrete Mathematics\u00a0285(1-3), 83\u201395 (2004)","journal-title":"Discrete Mathematics"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/3-540-45465-9_31","volume-title":"Automata, Languages and Programming","author":"L. Gargano","year":"2002","unstructured":"Gargano, L., Hell, P., Stacho, L., Vaccaro, U.: Spanning trees with bounded number of branch vertices. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 355\u2013365. Springer, Heidelberg (2002)"},{"issue":"4","key":"4_CR7","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S. Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica\u00a020(4), 374\u2013387 (1998)","journal-title":"Algorithmica"},{"key":"4_CR8","unstructured":"Khuller, S., Bhatia, R., Pless, R.: On local search and placement of meters in networks. In: Proc. of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 319\u2013328 (2000)"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-3-642-03367-4_40","volume-title":"Algorithms and Data Structures","author":"M. Knauer","year":"2009","unstructured":"Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 459\u2013470. Springer, Heidelberg (2009)"},{"key":"4_CR10","unstructured":"Lu, H.I., Ravi, R.: The power of local optimization: Approximation algorithms for maximum-leaf spanning tree. In: Proceedings of the Thirtieth Annual Allerton Conference on Communication, Control and Computing, pp. 533\u2013542 (1992)"},{"issue":"3","key":"4_CR11","first-page":"308","volume":"12","author":"E. Prieto","year":"2005","unstructured":"Prieto, E., Sloper, C.: Reducing to independent set structure \u2013 the case of k-internal spanning tree. Nordic Journal of Computing\u00a012(3), 308\u2013318 (2005)","journal-title":"Nordic Journal of Computing"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.ipl.2007.08.030","volume":"105","author":"G. Salamon","year":"2008","unstructured":"Salamon, G., Wiener, G.: On finding spanning trees with few leaves. Information Processing Letters\u00a0105, 164\u2013169 (2008)","journal-title":"Information Processing Letters"},{"issue":"50","key":"4_CR13","doi-asserted-by":"publisher","first-page":"5273","DOI":"10.1016\/j.tcs.2009.08.029","volume":"410","author":"G. Salamon","year":"2009","unstructured":"Salamon, G.: Approximating the maximum internal spanning tree problem. Theoretical Computer Science\u00a0410(50), 5273\u20135284 (2009)","journal-title":"Theoretical Computer Science"},{"key":"4_CR14","unstructured":"Salamon, G.: Degree-Based Spanning Tree Optimization. PhD thesis, Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Hungary (2010)"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/978-3-642-20662-7_36","volume-title":"Experimental Algorithms","author":"D.M. Silva","year":"2011","unstructured":"Silva, D.M., Silva, R.M.A., Mateus, G.R., Gon\u00e7alves, J.F., Resende, M.G.C., Festa, P.: An iterative refinement algorithm for the minimum branch vertices problem. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol.\u00a06630, pp. 421\u2013433. Springer, Heidelberg (2011)"},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/3-540-68530-8_37","volume-title":"Algorithms - ESA \u201998","author":"R. Solis-Oba","year":"1998","unstructured":"Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with maximum number of leaves. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 441\u2013452. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38016-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T15:13:05Z","timestamp":1557673985000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38016-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642380150","9783642380167"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38016-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}