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

Osipov, Vitali

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

学位論文

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

MPS-Authors

Osipov, Vitali
International Max Planck Research School, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

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

引用: https://hdl.handle.net/11858/00-001M-0000-0027-D5A8-7

要旨

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.