de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45136

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

Locator
There are no locators available
Fulltext (public)

1998-1-010
(Any fulltext), 10KB

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: http://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