{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:58Z","timestamp":1771036378466,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,9,28]],"date-time":"2010-09-28T00:00:00Z","timestamp":1285632000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00453-010-9454-5","type":"journal-article","created":{"date-parts":[[2010,9,27]],"date-time":"2010-09-27T12:10:56Z","timestamp":1285589456000},"page":"882-897","source":"Crossref","is-referenced-by-count":13,"title":["A New Algorithm for Finding Trees with Many Leaves"],"prefix":"10.1007","volume":"61","author":[{"given":"Joachim","family":"Kneis","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Langer","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,9,28]]},"reference":[{"key":"9454_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/978-3-540-75183-0","volume-title":"Proceedings of the 27th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","author":"N. Alon","year":"2007","unstructured":"Alon, N., Fomin, F.V., Gutin, G., Krivelevich, M., Saurabh, S.: Better algorithms and bounds for directed maximum leaf problems. In: Proceedings of the 27th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Lecture Notes in Computer Science, vol. 4855, pp. 316\u2013327. Springer, Berlin (2007)"},{"key":"9454_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1007\/978-3-540-73420-8_32","volume-title":"Proceedings of the 34th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"N. Alon","year":"2007","unstructured":"Alon, N., Fomin, F.V., Gutin, G., Krivelevich, M., Saurabh, S.: Parameterized algorithms for directed maximum leaf problems. In: Proceedings of the 34th International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 4596, pp. 352\u2013362. Springer, Berlin (2007)"},{"issue":"1","key":"9454_CR3","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1137\/070710494","volume":"23","author":"N. Alon","year":"2008","unstructured":"Alon, N., Fomin, F.V., Gutin, G., Krivelevich, M., Saurabh, S.: Spanning directed trees with many leaves. SIAM J. Discrete Math. 23(1), 466\u2013476 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"9454_CR4","series-title":"Springer Monographs in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84800-998-1","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"J. Bang-Jensen","year":"2009","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer Monographs in Mathematics. Springer, Berlin (2009)","edition":"2"},{"issue":"1","key":"9454_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: On linear time minor tests with depth-first search. J. Algorithms 14(1), 1\u201323 (1993). DOI 10.1006\/jagm.1993.1001","journal-title":"J. Algorithms"},{"key":"9454_CR6","unstructured":"Bonsma, P.: Sparse cuts, matching-cuts and leafy trees in graphs. Ph.D. thesis, University of Twente, the Netherlands (2006)"},{"issue":"3","key":"9454_CR7","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1137\/060664318","volume":"22","author":"P. Bonsma","year":"2008","unstructured":"Bonsma, P.: Spanning trees with many leaves in graphs with minimum degree three. SIAM J. Discrete Math. 22(3), 920\u2013937 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"9454_CR8","unstructured":"Bonsma, P.S., Dorn, F.: An FPT algorithm for directed spanning k-leaf (2007). arXiv:0711.4052"},{"key":"9454_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1007\/978-3-540-87744-8_19","volume-title":"Proceedings of the 16th European Symposium on Algorithms (ESA)","author":"P.S. Bonsma","year":"2008","unstructured":"Bonsma, P.S., Dorn, F.: Tight bounds and faster algorithms for directed max-leaf problems. In: Proceedings of the 16th European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 5193, pp. 222\u2013233. Springer, Berlin (2008)"},{"key":"9454_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-44793-1","volume-title":"Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"P.S. Bonsma","year":"2008","unstructured":"Bonsma, P.S., Zickfeld, F.: A 3\/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs. In: Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol. 5344. Springer, Berlin (2008)"},{"key":"9454_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1007\/978-3-540-78773-0_46","volume-title":"Proceedings of the 8th Symposium on Latin American Theoretical Informatics (LATIN)","author":"P.S. Bonsma","year":"2008","unstructured":"Bonsma, P.S., Zickfeld, F.: Spanning trees with many leaves in graphs without diamonds and blossoms. In: Proceedings of the 8th Symposium on Latin American Theoretical Informatics (LATIN). Lecture Notes in Computer Science, vol. 4957, pp. 531\u2013543. Springer, Berlin (2008)"},{"key":"9454_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-3-540-45138-9_20","volume-title":"Proceedings of the 28th Conference on Mathematical Foundations of Computer Science (MFCS)","author":"P.S. Bonsma","year":"2003","unstructured":"Bonsma, P.S., Br\u00fcggemann, T., Woeginger, G.J.: A faster fpt algorithm for finding spanning trees with many leaves. In: Proceedings of the 28th Conference on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science, vol. 2747, pp. 259\u2013268. Springer, Berlin (2003)"},{"issue":"10","key":"9454_CR13","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1109\/TPDS.2004.48","volume":"15","author":"F. Dai","year":"2004","unstructured":"Dai, F., Wu, J.: An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. Parallel Distrib. Syst. 15(10), 908\u2013920 (2004)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9454_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/978-3-642-11269-0_7","volume-title":"Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC)","author":"J. Daligault","year":"2009","unstructured":"Daligault, J., Thomass\u00e9, S.: On finding directed trees with many leaves. In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC). Lecture Notes in Computer Science, vol. 5917, pp. 86\u201397. Springer, Berlin (2009)"},{"issue":"2","key":"9454_CR15","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-leaf problem. J. Comput. Syst. Sci. 76(2), 144\u2013152 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"9454_CR16","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized computational feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 219\u2013244. Birkh\u00e4user, Boston (1995)"},{"key":"9454_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"3","key":"9454_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1798596.1798599","volume":"6","author":"M. Drescher","year":"2010","unstructured":"Drescher, M., Vetta, A.: An approximation algorithm for the maximum leaf spanning arborescence problem. ACM Trans. Algorithms 6(3), 1\u201318 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9454_CR19","first-page":"1","volume-title":"Proceedings of the 1st Workshop on Algorithms and Complexity in Durham (ACiD)","author":"V. Estivill-Castro","year":"2005","unstructured":"Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: FPT is P-time extremal structure I. In: Proceedings of the 1st Workshop on Algorithms and Complexity in Durham (ACiD), pp. 1\u201341 (2005)"},{"key":"9454_CR20","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1137\/0405010","volume":"5","author":"M.R. Fellows","year":"1992","unstructured":"Fellows, M.R., Langston, M.A.: On well-partial-ordering theory and its applications to combinatorial problems in VLSI design. SIAM J. Discrete Math. 5, 117\u2013126 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"9454_CR21","first-page":"240","volume-title":"Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","author":"M.R. Fellows","year":"2000","unstructured":"Fellows, M.R., McCartin, C., Rosamond, F.A., Stege, U.: Coordinatized kernels and catalytic reductions: An improved fpt algorithm for max leaf spanning tree and other problems. In: Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 240\u2013251. Springer, Berlin (2000)"},{"key":"9454_CR22","unstructured":"Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: On out-trees with many leaves. In: Proceedings of the 26th Symposium on Theoretical Aspects of Computer Science (STACS). Dagstuhl Seminar Proceedings, vol. 09001, pp. 421\u2013432. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany (2009)"},{"key":"9454_CR23","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"2","key":"9454_CR24","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s00453-007-9145-z","volume":"52","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Solving connected dominating set faster than 2 n . Algorithmica 52(2), 153\u2013166 (2008)","journal-title":"Algorithmica"},{"issue":"1","key":"9454_CR25","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). DOI 10.1016\/0020-0190(94)90139-2","journal-title":"Inf. Process. Lett."},{"key":"9454_CR26","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"9454_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-540-68880-8_23","volume-title":"Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM)","author":"G. Gutin","year":"2008","unstructured":"Gutin, G., Razgon, I., Kim, E.J.: Minimum leaf out-branching problems. In: Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM). Lecture Notes in Computer Science, vol. 5034, pp. 235\u2013246. Springer, Berlin (2008)"},{"issue":"4","key":"9454_CR28","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzio","year":"2001","unstructured":"Impagliazzio, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9454_CR29","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1137\/0404010","volume":"4","author":"D.J. Kleitman","year":"1991","unstructured":"Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SIAM J. Discrete Math. 4(1), 99\u2013106 (1991). DOI 10.1137\/0404010","journal-title":"SIAM J. Discrete Math."},{"key":"9454_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1007\/978-3-642-02927-1_54","volume-title":"Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP), Part I","author":"I. Koutis","year":"2009","unstructured":"Koutis, I., Williams, R.: Limits and applications of group algebras for parameterized problems. In: Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP), Part I. Lecture Notes in Computer Science, vol. 5555, pp. 653\u2013664. Springer, Berlin (2009)"},{"key":"9454_CR31","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1145\/513800.513815","volume-title":"Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC)","author":"W. Liang","year":"2002","unstructured":"Liang, W.: Constructing minimum-energy broadcast trees in wireless ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 112\u2013122. ACM, New York (2002). DOI 10.1145\/513800.513815"},{"key":"9454_CR32","unstructured":"Linial, N., Sturtevant, D.: Unpublished result (1987)"},{"key":"9454_CR33","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"9454_CR34","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/1288107.1288111","volume-title":"Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC)","author":"M.A. Park","year":"2007","unstructured":"Park, M.A., Willson, J., Wang, C., Thai, M., Wu, W., Farago, A.: A dominating and absorbent set in a wireless ad-hoc network with different transmission ranges. In: Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 22\u201331. ACM, New York (2007)"},{"key":"9454_CR35","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XIII: The disjoint paths problem. J. Comb. Theory Ser. B 63, 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9454_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/3-540-68530-8_37","volume-title":"Proceedings of the 6th European Symposium on Algorithms (ESA)","author":"R. Solis-Oba","year":"1998","unstructured":"Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with maximum number of leaves. In: Proceedings of the 6th European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 1461, pp. 441\u2013452. Springer, Berlin (1998)"},{"issue":"7","key":"9454_CR37","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1109\/TMC.2007.1034","volume":"6","author":"M. Thai","year":"2007","unstructured":"Thai, M., Wang, F., Liu, D., Zhu, S., Du, D.: Connected dominating sets in wireless networks with different transmission ranges. IEEE Trans. Mob. Comput. 6(7), 721\u2013730 (2007)","journal-title":"IEEE Trans. Mob. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9454-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9454-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9454-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T23:13:24Z","timestamp":1559690004000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9454-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,28]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9454"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9454-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9,28]]}}}