A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves


Share/Save/Bookmark

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 (pp. pp. 259-268).

[img] PDF
Restricted to UT campus only
: Request a copy
147kB
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:
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

 

Repository Staff Only: item control page

Metis ID: 213359