𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Better Approximation Algorithm for Finding Planar Subgraphs

✍ Scribed by Gruia Călinescu; Cristina G Fernandes; Ulrich Finkler; Howard Karloff

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
321 KB
Volume
27
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

The MAXIMUM PLANAR SUBGRAPH problemᎏgiven a graph G, find a largest planar subgraph of Gᎏhas applications in circuit layout, facility layout, and graph drawing. No previous polynomial-time approximation algorithm for this NP-Complete problem was known to achieve a performance ratio larger than 1r3, which is achieved simply by producing a spanning tree of G. We present the first approximation algorithm for MAXIMUM PLANAR SUBGRAPH with higher Ž . performance ratio 4r9 instead of 1r3 . We also apply our algorithm to find large outerplanar subgraphs. Last, we show that both MAXIMUM PLANAR SUB-GRAPH and its complement, the problem of removing as few edges as possible to leave a planar subgraph, are Max SNP-Hard.

📜 SIMILAR VOLUMES

A 3-Approximation Algorithm for Finding
A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
✍ Yefim Dinitz; Zeev Nutov 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 103 KB

The problem of finding a minimum weight k-vertex connected spanning sub-Ž . graph in a graph G s V, E is considered. For k G 2, this problem is known to be NP-hard. Based on the paper of Auletta, Dinitz, Nutov, and Parente in this issue, Ä 4 we derive a 3-approximation algorithm for k g 4, 5 . This

A 2-Approximation Algorithm for Finding
A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
✍ Vincenzo Auletta; Yefim Dinitz; Zeev Nutov; Domenico Parente 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 71 KB

The problem of finding a minimum weight k-vertex connected spanning sub-Ž . graph in a graph G s V, E is considered. For k G 2, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs Ž and of k-out-connected graphs i.e., graphs which contain a vertex

A Better Approximation Ratio for the Min
A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
✍ Cristina G Fernandes 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 213 KB

Consider the minimum size k-edge-connected spanning subgraph problem: given a positive integer k and a k-edge-connected graph G, find a k-edge-connected spanning subgraph of G with the minimum number of edges. This problem is known to be NP-complete. Khuller and Raghavachari presented the first algo

A Better Approximation for Balls
A Better Approximation for Balls
✍ Gerald H.L. Cheang; Andrew R. Barron 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 209 KB