A faster FPT algorithm for max-leaf spanning trees

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

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

A faster FPT algorithm for max-leaf spanning trees

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

Stochastic Operations Research

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

33 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 language	English
Title of host publication	Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003, Bratislava, Slovakia, August 25-29, 2003)
Editors	B. Rovan, P. Vojtás
Place of Publication	Berlin
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

Publication series

Name	Lecture Notes in Computer Science
Volume	2747
ISSN (Print)	0302-9743

Access to Document

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

Cite this

Bonsma, P. S., Brüggemann, T., & Woeginger, G. J. (2003). A faster FPT algorithm for max-leaf spanning trees. In B. Rovan, & P. Vojtás (Eds.), Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003, Bratislava, Slovakia, August 25-29, 2003) (pp. 259-268). (Lecture Notes in Computer Science; Vol. 2747). Springer. https://doi.org/10.1007/978-3-540-45138-9_20

@inproceedings{a232bcabc57b44beb0c9ae97b96a1333,

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

author = "P.S. Bonsma and T. Br{\"u}ggemann and G.J. 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 = "B. Rovan and P. Vojt{\'a}s",

booktitle = "Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003, Bratislava, Slovakia, August 25-29, 2003)",

address = "Germany",

}

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

A faster FPT algorithm for max-leaf spanning trees. / Bonsma, P.S.; Brüggemann, T.; Woeginger, G.J.
Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003, Bratislava, Slovakia, August 25-29, 2003). ed. / B. Rovan; P. Vojtás. Berlin: 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 - Brüggemann, T.

AU - Woeginger, G.J.

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.

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, Bratislava, Slovakia, August 25-29, 2003)

A2 - Rovan, B.

A2 - Vojtás, P.

PB - Springer

CY - Berlin

ER -

Bonsma PS, Brüggemann T, Woeginger GJ. A faster FPT algorithm for max-leaf spanning trees. In Rovan B, Vojtás P, editors, Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003, Bratislava, Slovakia, August 25-29, 2003). Berlin: Springer. 2003. p. 259-268. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-45138-9_20

A faster FPT algorithm for max-leaf spanning trees

Abstract

Publication series

Access to Document

Fingerprint

Cite this