Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 DetailsÜbersicht
  2-Approximation algorithm for finding a spanning tree with maximum number of leaves

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.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-7BD6-0 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-9BC3-3
Genre: Bericht

Dateien

einblenden: Dateien
ausblenden: Dateien
:
1998-1-010 (beliebiger Volltext), 10KB
Öffnen   Speichern
Datei-Permalink:
https://hdl.handle.net/11858/00-001M-0000-0014-7BD8-C
Name:
1998-1-010
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
text/html / [MD5]
Technische Metadaten:
Öffnen
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Solis-Oba, Roberto1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 1998
 Publikationsstatus: Erschienen
 Seiten: 16 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-010
Reportnr.: MPI-I-1998-1-010
BibTex Citekey: Solis-Oba98
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -