de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Hochschulschrift

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

MPG-Autoren

Osipov,  Vitali
International Max Planck Research School, 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

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


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0027-D5A8-7
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.