Item Details

Print View

Improved Approximation of Maximun Planar Subgraph

Zelikovsky, Alexander
Format
Report
Author
Zelikovsky, Alexander
Abstract
The maximum planar subgraph problem (MPSP) asks for a planar subgraph of a given graph with the maximum total cost. We suggest a new approximation algorithm for the weighted MPSP. We show that it has performance ratio of 5/12 in the case of graphs where the maxumum cost of an edge is at most twice the minimum cost of an edge. For the variant of MPSP that asks for an outerplanar graph, the algorithm suggested is the first with the higher performance ratio (7/12 instead of 1/2).
Language
English
Date Received
2012-10-29
Published
University of Virginia, Department of Computer Science, 1996
Published Date
1996
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online