A faster FPT algorithm for max-leaf spanning trees

P.S. Bonsma, T. Brüggemann, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

33 Citations (Scopus)


We describe a new, fast, and fairly simple FPT algorithm for the problem of deciding whether a given input graph G has a spanning tree with at least k leaves. The time complexity of our algorithm is polynomially bounded in the size of G, and its dependence on k is roughly O(9.49 k ). This is the fastest currently known algorithm for this problem.
Original languageEnglish
Title of host publicationProceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003, Bratislava, Slovakia, August 25-29, 2003)
EditorsB. Rovan, P. Vojtás
Place of PublicationBerlin
ISBN (Print)3-540-40671-9
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'A faster FPT algorithm for max-leaf spanning trees'. Together they form a unique fingerprint.

Cite this