Abstract
We present an algorithm that finds trees with at least k leaves in undirected and directed graphs. These problems are known as Maximum Leaf Spanning Tree for undirected graphs, and, respectively, Directed Maximum Leaf Out-Tree and Directed Maximum Leaf Spanning Out-Tree in the case of directed graphs. The run time of our algorithm is \(O({\it poly}(|V|) + 4^k k^2)\) on undirected graphs, and O(4k |V| ·|E|) on directed graphs. This improves over the previously fastest algorithms for these problems with run times of \(O({\it poly}(|V|) + 6.75^k {\it poly}(k))\) and \(2^{O(k \log k)} {\it poly}(|V|)\), respectively.
Supported by the DFG under grant RO 927/7-1.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Fomin, F.V., Gutin, G., Krivelevich, M., Saurabh, S.: Better algorithms and bounds for directed maximum leaf problems. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol. 4855, pp. 316–327. Springer, Heidelberg (2007)
Alon, N., Fomin, F.V., Gutin, G., Krivelevich, M., Saurabh, S.: Parameterized algorithms for directed maximum leaf problems. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 352–362. Springer, Heidelberg (2007)
Bodlaender, H.L.: On linear time minor tests with depth-first search. J. Algorithms 14(1), 1–23 (1993)
Bonsma, P.: Sparse cuts, matching-cuts and leafy trees in graphs. PhD thesis, University of Twente, the Netherlands (2006)
Bonsma, P.S., Brüggemann, T., Woeginger, G.J.: A faster FPT algorithm for finding spanning trees with many leaves. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 259–268. Springer, Heidelberg (2003)
Bonsma, P.S., Dorn, F.: An FPT algorithm for directed spanning k-leaf (2007), http://arxiv.org/abs/0711.4052
Bonsma, P.S., Dorn, F.: Tight Bounds and Faster Algorithms for Directed Max-Leaf Problems. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 222–233. Springer, Heidelberg (2008)
Bonsma, P.S., Zickfeld, F.: A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs. In: Proc. of the 34th WG. LNCS. Springer, Heidelberg (to appear, 2008)
Bonsma, P.S., Zickfeld, F.: Spanning trees with many leaves in graphs without diamonds and blossoms. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 531–543. Springer, Heidelberg (2008)
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–920 (2004)
Downey, R.G., Fellows, M.R.: Parameterized computational feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 219–244. Birkhäuser, Boston (1995)
Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: FPT is P-time extremal structure I. In: Proc. of the 1st ACiD, pp. 1–41 (2005)
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–126 (1992)
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: Kapoor, S., Prasad, S. (eds.) FST TCS 2000. LNCS, vol. 1974, pp. 240–251. Springer, Heidelberg (2000)
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–49 (1994)
Gutin, G., Razgon, I., Kim, E.J.: Minimum Leaf Out-Branching Problems. In: Fleischer, R., Xu, J. (eds.) AAIM 2008. LNCS, vol. 5034, pp. 235–246. Springer, Heidelberg (2008)
Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SIAM J. Discret. Math. 4(1), 99–106 (1991)
Liang, W.: Constructing minimum-energy broadcast trees in wireless ad hoc networks. In: Proc. of 3rd MOBIHOC, pp. 112–122. ACM, New York (2002)
Linial, N., Sturtevant, D.: Unpublished result (1987)
Lu, H., Ravi, R.: Approximating maximum leaf spanning trees in almost linear time. J. Algorithms 29(1), 132–141 (1998)
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: Proc. of the 8th MOBIHOC, pp. 22–31. ACM, New York (2007)
Robertson, N., Seymour, P.D.: Graph minors—a survey. In: Anderson, I. (ed.) Surveys in Combinatorics, pp. 153–171. Cambridge University Press, Cambridge (1985)
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. 1461, pp. 441–452. Springer, Heidelberg (1998)
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–730 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kneis, J., Langer, A., Rossmanith, P. (2008). A New Algorithm for Finding Trees with Many Leaves. In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-92182-0_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92181-3
Online ISBN: 978-3-540-92182-0
eBook Packages: Computer ScienceComputer Science (R0)