𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A New Approximation Algorithm for Finding Heavy Planar Subgraphs

✍ Scribed by Gruia Călinescu, Cristina G. Fernandes, Howard Karloff and Alexander Zelikovsky

Book ID
120136589
Publisher
Springer
Year
2003
Tongue
English
Weight
185 KB
Volume
36
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A Better Approximation Algorithm for Fin
A Better Approximation Algorithm for Finding Planar Subgraphs
✍ Gruia Călinescu; Cristina G Fernandes; Ulrich Finkler; Howard Karloff 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 321 KB

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,

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