English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-D5A8-7 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-D5A9-5
Genre: Thesis

Files

show Files
hide Files
:
Masterarbeit-Osipov-2006.pdf (Any fulltext), 251KB
 
File Permalink:
-
Name:
Masterarbeit-Osipov-2006.pdf
Description:
-
OA-Status:
Visibility:
Restricted (Max Planck Institute for Informatics, MSIN; )
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Osipov, Vitali1, Author
Bläser^, Markus2, Advisor
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              

Content

show
hide
Free keywords: -
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2006-08-252006
 Publication Status: Issued
 Pages: -
 Publishing info: Saarbrücken : Universität des Saarlandes
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: Osipov2006
 Degree: Master

Event

show

Legal Case

show

Project information

show

Source

show