English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves

MPS-Authors
/persons/resource/persons45136

Solis-Oba,  Roberto
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Solis-Oba, R. (1998). 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves. In G. Bilardi, G. F. Italiano, A. Pietracaprina, & G. Pucci (Eds.), Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98) (pp. 441-452). Berlin, Germany: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-373E-5
Abstract
The preoblem of finding a spanning tree with maximum number of leaves is studied. A simple 2-approximation algorithm for the problem is presented. The variant of the problem in which a given set of vertices must be leaves of the spanning tree is also studied. A 5/2-approximation algorithm for this version of the problem is presented.