非表示:
キーワード:
-
要旨:
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.
