Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Bachelor's and Master's Theses

Vitaly Osipov: A Polynomial Time Randomized Parallel Approximation Algorithm for Finding Heavy Planar Subgraphs

Master's Thesis, 2006.

Advisor: Prof. Dr. Markus Bläser

We provide an approximation algorithm for the Maximum Weight Planar Subgraph, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. Our algorithm has performance ratio in general case at least 1/3 + 1/72 meeting one of the best known algorithm, though in several special cases we prove stronger results. In particular, we derive performance ratio 2/3 (instead of 7/12) for the NP-hard Maximum Weight Outerplanar Subgraph problem meeting performance ratio of the best known algorithm for the unweighted case. When the maximum 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.