A faster FPT algorithm for max-leaf spanning trees

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

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    21 Citaten (Scopus)

    Samenvatting

    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.
    Originele taal-2Engels
    TitelProceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003, Bratislava, Slovakia, August 25-29, 2003)
    RedacteurenB. Rovan, P. Vojtás
    Plaats van productieBerlin
    UitgeverijSpringer
    Pagina's259-268
    ISBN van geprinte versie3-540-40671-9
    DOI's
    StatusGepubliceerd - 2003

    Publicatie series

    NaamLecture Notes in Computer Science
    Volume2747
    ISSN van geprinte versie0302-9743

    Citeer dit