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

    21 Citations (Scopus)

    Abstract

    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
    PublisherSpringer
    Pages259-268
    ISBN (Print)3-540-40671-9
    DOIs
    Publication statusPublished - 2003

    Publication series

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

    Cite this