2-Approximation algorithm for finding a spanning tree with maximum number of 
leaves

Solis-Oba, Roberto

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Report

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)

MPI-I-98-1-010.pdf
(Any fulltext), 204KB

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 (MPI-I-1998-1-010). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-7BD6-0

Abstract

We study the problem of finding a spanning tree with maximum number of leaves. We present a simple 2-approximation algorithm for the problem, improving on the previous best performance ratio of 3 achieved by algorithms of Ravi and Lu. Our algorithm can be implemented to run in linear time using simple data structures. We also study the variant of the problem in which a given subset of vertices are required to be leaves in the tree. We provide a 5/2-approximation algorithm for this version of the problem