Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

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

MPG-Autoren
/persons/resource/persons45136

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-373E-5
Zusammenfassung
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.