{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T18:47:45Z","timestamp":1771354065552,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,6,15]],"date-time":"2014-06-15T00:00:00Z","timestamp":1402790400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1007\/s00224-014-9556-6","type":"journal-article","created":{"date-parts":[[2014,6,19]],"date-time":"2014-06-19T13:25:15Z","timestamp":1403184315000},"page":"181-196","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Approximating Spanning Trees with Few Branches"],"prefix":"10.1007","volume":"56","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","published-online":{"date-parts":[[2014,6,15]]},"reference":[{"key":"9556_CR1","unstructured":"Bhatia, R., Khuller, S., Pless, R., Sussmann, Y.J.: The full degree spanning tree problem. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999), pp. 864\u2013865 (1999)"},{"issue":"2","key":"9556_CR2","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/s10589-013-9556-5","volume":"56","author":"F Carrabs","year":"2013","unstructured":"Carrabs, F., Cerulli, R., Gaudioso, M., Gentili, M.: Lower and upper bounds for the spanning tree with minimum branch vertices. Comp. Opt. Appl. 56 (2), 405\u2013438 (2013)","journal-title":"Comp. Opt. Appl."},{"issue":"3","key":"9556_CR3","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/j.ejor.2013.07.029","volume":"232","author":"C Cerrone","year":"2014","unstructured":"Cerrone, C., Cerulli, R., Raiconi, A.: Relations, models and a memetic approach for three degree-dependent spanning tree problems. Eur. J. Oper. Res. 232 (3), 442\u2013453 (2014)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"9556_CR4","doi-asserted-by":"crossref","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. Comput. Optim. Appl. 42 (3), 353\u2013370 (2009). doi: 10.1007\/s10589-007-9120-2","journal-title":"Comput. Optim. Appl."},{"key":"9556_CR5","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum degree spanning tree to within one from the optimal degree. In: Proceedings of the Third Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201992), pp. 317\u2013324 (1992)"},{"key":"9556_CR6","doi-asserted-by":"crossref","unstructured":"Gargano, L., Hammar, M.: There are spanning spiders in dense graphs (and we know how to find them. In: Proceedings 30th International Colloquium on Automata, Languages and Programming (ICALP\u201903), Lecture Notes in Computer Science, vol. 2719, pp. 802\u2013816 (2003)","DOI":"10.1007\/3-540-45061-0_63"},{"issue":"1-3","key":"9556_CR7","doi-asserted-by":"crossref","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. Discret. Math. 285 (1-3), 83\u201395 (2004). doi: 10.1016\/j.disc.2004.04.005","journal-title":"Discret. Math."},{"key":"9556_CR8","doi-asserted-by":"crossref","unstructured":"Gargano, L., Hell, P., Stacho, L., Vaccaro, U.: Spanning trees with bounded number of branch vertices. In: Proceedings 29th Intenational Colloquium on Automata, Languages and Programming (ICALP\u201902), Lecture Notes in Computer Science, vol. 2380, pp. 355\u2013365 (2002)","DOI":"10.1007\/3-540-45465-9_31"},{"issue":"4","key":"9556_CR9","doi-asserted-by":"crossref","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 20 (4), 374\u2013387 (1998)","journal-title":"Algorithmica"},{"key":"9556_CR10","unstructured":"Khuller, S., Bhatia, R., Pless, R.: On local search and placement of meters in networks. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900), pp. 319\u2013328 (2000)"},{"key":"9556_CR11","doi-asserted-by":"crossref","unstructured":"Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. In: Proceedings of the 11th Algorithms and Data Structures Symposium (WADS\u201909), Lecture Notes in Computer Science, vol. 5664, pp. 459\u2013470 (2009)","DOI":"10.1007\/978-3-642-03367-4_40"},{"key":"9556_CR12","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":"1","key":"9556_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18 (1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"9556_CR14","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. Nord. J. Comput. 12 (3), 308\u2013318 (2005)","journal-title":"Nord. J. Comput."},{"key":"9556_CR15","doi-asserted-by":"crossref","unstructured":"Rossi, A., Singh, A., Sundar, S.: Cutting-plane-based algorithms for two branch vertices related spanning tree problems. Optim. Eng., 1\u201333 (2013)","DOI":"10.1007\/s11081-013-9219-5"},{"issue":"50","key":"9556_CR16","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 410 (50), 5273\u20135284 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9556_CR17","volume-title":"Degree-based Spanning tree Optimization. Ph.D. Thesis, Department of Computer Science and Information Theory","author":"G Salamon","year":"2010","unstructured":"Salamon, G.: Degree-based Spanning tree Optimization. Ph.D. Thesis, Department of Computer Science and Information Theory. Budapest University of Technology and Economics, Hungary (2010)"},{"key":"9556_CR18","doi-asserted-by":"crossref","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. Inf. Process. Lett. 105, 164\u2013169 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9556_CR19","doi-asserted-by":"crossref","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: Proceedinsgs 10th International Symposium on Experimental Algorithms (SEA\u201911), Lecture Notes in Computer Science, vol. 6630, pp. 421\u2013433 (2011)","DOI":"10.1007\/978-3-642-20662-7_36"},{"key":"9556_CR20","doi-asserted-by":"crossref","unstructured":"Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with maximum number of leaves. In: Proceedings of the 6th Annual European Symposium on Algorithms (ESA\u201998), Lecture Notes in Computer Science, vol. 1461, pp. 441\u2013452 (1998)","DOI":"10.1007\/3-540-68530-8_37"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9556-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9556-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9556-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T18:36:02Z","timestamp":1565548562000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9556-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,15]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["9556"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9556-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,15]]}}}