Campus Event Calendar
Event Entry
What and Who
A Polynomial Time Randomized Parallel Approximation Algorithm for Finding Heavy Planar Subgraphs
Vitaly Osipov
IMPRS
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 10 July 2006
08:30
330 Minutes
E1 4
024
Saarbrücken
Abstract
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
the best algorithm known so far, 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 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.
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
the best algorithm known so far, 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 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.
Contact
Kerstin Kathy Meyer-Ross
226
--email hidden
passcode not visible
logged in users only
Jennifer Gerling, 06/26/2006 13:14
Jennifer Gerling, 06/26/2006 11:57 -- Created document.
Jennifer Gerling, 06/26/2006 11:57 -- Created document.