A faster FPT algorithm for max-leaf spanning trees

P.S. Bonsma, T. Brueggemann, Gerhard 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)
EditorsBranislav Rovan, Peter Vojtas
PublisherSpringer
Pages259-268
ISBN (Print)3-540-40671-9
DOIs
Publication statusPublished - 2003
Event28th International Symposium on Mathematical Foundations of Computer Science, MFCS 2003 - Bratislava, Slovakia
Duration: 25 Aug 200329 Aug 2003
Conference number: 28

Publication series

NameLecture Notes in Computer Science
PublisherSpringer-Verlag
Volume2747
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th International Symposium on Mathematical Foundations of Computer Science, MFCS 2003
Abbreviated titleMFCS
CountrySlovakia
CityBratislava
Period25/08/0329/08/03

Keywords

  • METIS-213359
  • IR-72725

Cite this