{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T17:54:45Z","timestamp":1777398885937,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,10,13]],"date-time":"2015-10-13T00:00:00Z","timestamp":1444694400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["227829-2009"],"award-info":[{"award-number":["227829-2009"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s00453-015-0080-0","type":"journal-article","created":{"date-parts":[[2015,10,13]],"date-time":"2015-10-13T20:37:06Z","timestamp":1444768626000},"page":"374-388","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["A 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves"],"prefix":"10.1007","volume":"77","author":[{"given":"Roberto","family":"Solis-Oba","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Bonsma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefanie","family":"Lowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,10,13]]},"reference":[{"issue":"1","key":"80_CR1","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1137\/070710494","volume":"23","author":"N Alon","year":"2009","unstructured":"Alon, N., Fomin, F.V., Gutin, G., Krivelevich, M., Saurabh, S.: Spanning directed trees with many leaves. SIAM J. Discret. Math. 23(1), 466\u2013476 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"80_CR2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.jda.2012.03.006","volume":"15","author":"D Binkele-Raible","year":"2012","unstructured":"Binkele-Raible, D., Fernau, H.: An exact exponential-time algorithm for the directed maximum leaf spanning tree problem. J. Discret. Algorithms 15, 43\u201355 (2012)","journal-title":"J. Discret. Algorithms"},{"key":"80_CR3","doi-asserted-by":"crossref","unstructured":"Binkele-Raible, D., Fernau, H., Fomin, F.V., Lokshtanov, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: on out-trees with many leaves. ACM Trans. Algorithms 8(4) (2012) (Article 38)","DOI":"10.1145\/2344422.2344428"},{"issue":"1","key":"80_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: On linear time minor tests with depth-first search. J. Algorithms 14(1), 1\u201323 (1993)","journal-title":"J. Algorithms"},{"key":"80_CR5","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.jda.2011.06.005","volume":"12","author":"P Bonsma","year":"2012","unstructured":"Bonsma, P.: Max-leaves spanning tree is APX-hard for cubic graphs. J. Discret. Algorithms 12, 14\u201323 (2012)","journal-title":"J. Discret. Algorithms"},{"key":"80_CR6","doi-asserted-by":"crossref","unstructured":"Bonsma, P., Brueggemann, T., Woeginger, G.J.: A faster FPT algorithm for finding spanning trees with many leaves. In: Mathematical Foundations of Computer Science (MFCS 2003). Volume 2747 of Lecture Notes in Computer Science, pp. 259\u2013268. Springer, Berlin (2003)","DOI":"10.1007\/978-3-540-45138-9_20"},{"key":"80_CR7","doi-asserted-by":"crossref","unstructured":"Bonsma, P., Dorn, F.: Tight bounds and a fast FPT algorithm for directed max-leaf spanning tree. ACM Trans. Algorithms 7(4) (2011) (Article 44)","DOI":"10.1145\/2000807.2000812"},{"issue":"4","key":"80_CR8","doi-asserted-by":"crossref","first-page":"1652","DOI":"10.1137\/100801251","volume":"25","author":"P Bonsma","year":"2011","unstructured":"Bonsma, P., Zickfeld, F.: A 3\/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs. SIAM J. Discret. Math. 25(4), 1652\u20131666 (2011)","journal-title":"SIAM J. Discret. Math."},{"issue":"6","key":"80_CR9","doi-asserted-by":"crossref","first-page":"1178","DOI":"10.1016\/j.disc.2011.11.043","volume":"312","author":"P Bonsma","year":"2012","unstructured":"Bonsma, P., Zickfeld, F.: Improved bounds for spanning trees with many leaves. Discret. Math. 312(6), 1178\u20131194 (2012)","journal-title":"Discret. Math."},{"key":"80_CR10","doi-asserted-by":"crossref","unstructured":"Correa, J.R., Fernandes, C.G., Matamala, M., Wakabayashi, Y.: A 5\/3-approximation for finding spanning trees with many leaves in cubic graphs. In: Approximation and Online Algorithms (WAOA 2007). Volume 4927 of Lecture Notes in Computer Science, pp. 184\u2013192. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-77918-6_15"},{"issue":"2","key":"80_CR11","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.jcss.2009.06.005","volume":"76","author":"J Daligault","year":"2010","unstructured":"Daligault, J., Gutin, G., Kim, E.J., Yeo, A.: FPT algorithms and kernels for the directed $$k$$ k -leaf problem. J. Comput. Syst. Sci. 76(2), 144\u2013152 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"80_CR12","doi-asserted-by":"crossref","unstructured":"Daligault, J., Thomass\u00e9, S.: On finding directed trees with many leaves. In: Parameterized and Exact Computation (IWPEC 2009). Volume 5917 of Lecture Notes in Computer Science, pp. 86\u201397. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-11269-0_7"},{"key":"80_CR13","doi-asserted-by":"crossref","unstructured":"Drescher, M., Vetta, A.: An approximation algorithm for the max leaf spanning arborescence problem. ACM Trans. Algorithms 6(3) (2010) (Article 46)","DOI":"10.1145\/1798596.1798599"},{"key":"80_CR14","unstructured":"Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: FPT is P-time extremal structure I. In: Algorithms and Complexity in Durham (ACiD 2005). Volume 4 of Texts in Algorithmics, pp. 1\u201341. King\u2019s College, London (2005)"},{"issue":"4","key":"80_CR15","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1007\/s00224-009-9167-9","volume":"45","author":"M Fellows","year":"2009","unstructured":"Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., Saurabh, S.: The complexity ecology of parameters: an illustration using bounded max leaf number. Theory Comput. Syst. 45(4), 822\u2013848 (2009)","journal-title":"Theory Comput. Syst."},{"issue":"45","key":"80_CR16","doi-asserted-by":"crossref","first-page":"6290","DOI":"10.1016\/j.tcs.2011.07.011","volume":"412","author":"H Fernau","year":"2011","unstructured":"Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Raible, D., Rossmanith, P.: An exact algorithm for the maximum leaf spanning tree problem. Theor. Comput. Sci. 412(45), 6290\u20136302 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"80_CR17","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1002\/net.20001","volume":"43","author":"T Fujie","year":"2004","unstructured":"Fujie, T.: The maximum-leaf spanning tree problem: formulations and facets. Networks 43(4), 212\u2013223 (2004)","journal-title":"Networks"},{"issue":"1","key":"80_CR18","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0020-0190(94)90139-2","volume":"52","author":"G Galbiati","year":"1994","unstructured":"Galbiati, G., Maffioli, F., Morzenti, A.: A short note on the approximability of the maximum leaves spanning tree problem. Inf. Process. Lett. 52(1), 45\u201349 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"80_CR19","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1002\/jgt.3190130604","volume":"13","author":"JR Griggs","year":"1989","unstructured":"Griggs, J.R., Kleitman, D.J., Shastri, A.: Spanning trees with many leaves in cubic graphs. J. Graph Theory 13(6), 669\u2013695 (1989)","journal-title":"J. Graph Theory"},{"issue":"2","key":"80_CR20","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0012-365X(92)90331-9","volume":"104","author":"JR Griggs","year":"1992","unstructured":"Griggs, J.R., Wu, M.: Spanning trees in graphs of minimum degree 4 or 5. Discret. Math. 104(2), 167\u2013183 (1992)","journal-title":"Discret. Math."},{"issue":"4","key":"80_CR21","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"},{"issue":"4","key":"80_CR22","doi-asserted-by":"crossref","first-page":"811","DOI":"10.7155\/jgaa.00279","volume":"16","author":"BMP Jansen","year":"2012","unstructured":"Jansen, B.M.P.: Kernelization for maximum leaf spanning tree with positive vertex weights. J. Graph Algorithms Appl. 16(4), 811\u2013846 (2012)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"80_CR23","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1007\/s10878-011-9383-5","volume":"25","author":"S Kamei","year":"2013","unstructured":"Kamei, S., Kakugawa, H., Devismes, S., Tixeuil, S.: A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks. J. Comb. Optim. 25(3), 430\u2013459 (2013)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"80_CR24","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1137\/0404010","volume":"4","author":"DJ Kleitman","year":"1991","unstructured":"Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SIAM J. Discret. Math. 4(1), 99\u2013106 (1991)","journal-title":"SIAM J. Discret. Math."},{"key":"80_CR25","doi-asserted-by":"crossref","unstructured":"Lory\u015b, K., Zwo\u017aniak, G.: Approximation algorithm for the maximum leaf spanning tree problem for cubic graphs. In: Algorithms-ESA 2002. Volume 2461 of Lecture Notes in Computer Science, pp. 686\u2013697. Springer, Berlin (2002)","DOI":"10.1007\/3-540-45749-6_60"},{"key":"80_CR26","unstructured":"Lu, H., 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":"80_CR27","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/jagm.1998.0944","volume":"29","author":"H Lu","year":"1998","unstructured":"Lu, H., Ravi, R.: Approximating maximum leaf spanning trees in almost linear time. J. Algorithms 29(1), 132\u2013141 (1998)","journal-title":"J. Algorithms"},{"issue":"3","key":"80_CR28","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0012-365X(84)90163-8","volume":"49","author":"C Payan","year":"1984","unstructured":"Payan, C., Tchuente, M., Xuong, N.H.: Arbres avec un nombre maximum de sommets pendants. Discret. Math. 49(3), 267\u2013273 (1984)","journal-title":"Discret. Math."},{"key":"80_CR29","doi-asserted-by":"crossref","unstructured":"Raible, D., Fernau, H.: An amortized search tree analysis for k-leaf spanning tree. In: SOFSEM 2010: Theory and Practice of Computer Science. Volume 5901 of Lecture Notes in Computer Science, pp. 672\u2013684. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-11266-9_56"},{"issue":"1\u20133","key":"80_CR30","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.tcs.2004.08.013","volume":"329","author":"L Ruan","year":"2004","unstructured":"Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.: A greedy approximation for minimum connected dominating sets. Theor. Comput. Sci. 329(1\u20133), 325\u2013330 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"80_CR31","doi-asserted-by":"crossref","unstructured":"Schwartges, N., Spoerhase, J., Wolff, A.: Approximation algorithms for the maximum leaf spanning tree problem on acyclic digraphs. In: Approximation and Online Algorithms (WAOA 2011). Volume 7164 of Lecture Notes in Computer Science, pp. 77\u201388. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-29116-6_7"},{"key":"80_CR32","doi-asserted-by":"crossref","unstructured":"Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with maximum number of leaves. In: Algorithms-ESA 1998. Volume 1461 of Lecture Notes in Computer Science, pp. 441\u2013452. Springer, Berlin (1998)","DOI":"10.1007\/3-540-68530-8_37"},{"key":"80_CR33","unstructured":"Solis-Oba, R.: 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves. Technical report TR 98-1-010. Max Planck Institute for Computer Science, Saarbruecken (1998). http:\/\/domino.mpi-inf.mpg.de\/internet\/reports.nsf\/NumberView\/1998-1-010"},{"issue":"1","key":"80_CR34","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/0020-0190(81)90141-1","volume":"13","author":"JA Storer","year":"1981","unstructured":"Storer, J.A.: Constructing full spanning trees for cubic graphs. Inf. Process. Lett. 13(1), 8\u201311 (1981)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0080-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0080-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0080-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0080-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:22Z","timestamp":1559072842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0080-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,13]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["80"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0080-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,13]]}}}