Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  A polynomial Time Randomized Parallel Approximation Algorithm for Finding Heavy Planar Subgraphs

Osipov, V. (2006). A polynomial Time Randomized Parallel Approximation Algorithm for Finding Heavy Planar Subgraphs. Master Thesis, Universität des Saarlandes, Saarbrücken.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
Masterarbeit-Osipov-2006.pdf (beliebiger Volltext), 251KB
 
Datei-Permalink:
-
Name:
Masterarbeit-Osipov-2006.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Eingeschränkt (Max Planck Institute for Informatics, MSIN; )
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Osipov, Vitali1, Autor
Bläser^, Markus2, Ratgeber
Affiliations:
1International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We provide an approximation algorithm for the Maximum Weight Planar Subgraph problem, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. In the general case our algorithm has performance ratio at least 1/3+1/72 matching the best algorithm known so far, though in several special cases we prove stronger results. In particular, we obtain performance ratio 2/3 (in- stead of 7/12) for the NP-hard Maximum Weight Outerplanar Sub- graph problem meeting the performance ratio of the best algorithm for the unweighted case. When the maximum weight planar subgraph is one of several special types of Hamiltonian graphs, we show performance ratios at least 2/5 and 4/9 (instead of 1/3 + 1/72), and 1/2 (instead of 4/9) for the unweighted case.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006-08-252006
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: Saarbrücken : Universität des Saarlandes
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: Osipov2006
 Art des Abschluß: Master

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: