A faster FPT algorithm for max-leaf spanning trees

P.S. Bonsma; T. Brueggemann; Gerhard Woeginger

doi:10.1007/978-3-540-45138-9_20

A faster FPT algorithm for max-leaf spanning trees

P.S. Bonsma
, T. Brueggemann
, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

34 Citations (Scopus)

4 Downloads (Pure)

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 language	English
Title of host publication	Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003)
Editors	Branislav Rovan, Peter Vojtas
Publisher	Springer
Pages	259-268
ISBN (Print)	3-540-40671-9
DOIs	https://doi.org/10.1007/978-3-540-45138-9_20
Publication status	Published - 2003
Event	28th International Symposium on Mathematical Foundations of Computer Science, MFCS 2003 - Bratislava, Slovakia Duration: 25 Aug 2003 → 29 Aug 2003 Conference number: 28

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag
Volume	2747
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	28th International Symposium on Mathematical Foundations of Computer Science, MFCS 2003
Abbreviated title	MFCS
Country/Territory	Slovakia
City	Bratislava
Period	25/08/03 → 29/08/03

Keywords

METIS-213359
IR-72725

Access to Document

10.1007/978-3-540-45138-9_20

Cite this

@inproceedings{d66edc9cb8be4997a285186d3c7aa172,

title = "A faster FPT algorithm for max-leaf spanning trees",

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.",

keywords = "METIS-213359, IR-72725",

author = "P.S. Bonsma and T. Brueggemann and Gerhard Woeginger",

year = "2003",

doi = "10.1007/978-3-540-45138-9\_20",

language = "English",

isbn = "3-540-40671-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "259--268",

editor = "Branislav Rovan and Peter Vojtas",

booktitle = "Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003)",

address = "Germany",

note = "28th International Symposium on Mathematical Foundations of Computer Science, MFCS 2003, MFCS ; Conference date: 25-08-2003 Through 29-08-2003",

}

Bonsma, PS, Brueggemann, T & Woeginger, G 2003, A faster FPT algorithm for max-leaf spanning trees. in B Rovan & P Vojtas (eds), Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003). Lecture Notes in Computer Science, vol. 2747, Springer, pp. 259-268, 28th International Symposium on Mathematical Foundations of Computer Science, MFCS 2003, Bratislava, Slovakia, 25/08/03. https://doi.org/10.1007/978-3-540-45138-9_20

A faster FPT algorithm for max-leaf spanning trees. / Bonsma, P.S.; Brueggemann, T.; Woeginger, Gerhard.
Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003). ed. / Branislav Rovan; Peter Vojtas. Springer, 2003. p. 259-268 (Lecture Notes in Computer Science; Vol. 2747).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A faster FPT algorithm for max-leaf spanning trees

AU - Bonsma, P.S.

AU - Brueggemann, T.

AU - Woeginger, Gerhard

N1 - Conference code: 28

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - METIS-213359

KW - IR-72725

U2 - 10.1007/978-3-540-45138-9_20

DO - 10.1007/978-3-540-45138-9_20

M3 - Conference contribution

SN - 3-540-40671-9

T3 - Lecture Notes in Computer Science

SP - 259

EP - 268

BT - Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003)

A2 - Rovan, Branislav

A2 - Vojtas, Peter

PB - Springer

T2 - 28th International Symposium on Mathematical Foundations of Computer Science, MFCS 2003

Y2 - 25 August 2003 through 29 August 2003

ER -

A faster FPT algorithm for max-leaf spanning trees

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this