A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves

Bonsma, Paul and Brueggemann, Tobias and Woeginger, Gerhard J. (2003) A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves. In: 28th International Symposium on Mathematical Foundations of Computer Science, MFCS, August 25-29, 2003, Bratislava, Slovakia.

PDF
Restricted to UT campus only: Request a copy
143Kb

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.
Item Type:	Conference or Workshop Item
Copyright:	© 2003 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/72725
Official URL:	http://dx.doi.org/10.1007/978-3-540-45138-9_20
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 213359