Two new approximation algorithms for the maximum planar subgraph problem

The maximum planar subgraph problem (MPS) is defined as follows: given a graph G, find a largest planar subgraph of G. The problem is NP-hard and it has applications in graph drawing and resource location optimization. Călinescu et al. [J. Alg. 27, 269-302 (1998)] presented the first approximation a...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerző: Poranen Timo
Dokumentumtípus: Cikk
Megjelent: 2008
Sorozat:Acta cybernetica 18 No. 3
Kulcsszavak:Számítástechnika, Kibernetika, Algoritmus
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12832
LEADER 02146nab a2200217 i 4500
001 acta12832
005 20220616153700.0
008 161015s2008 hu o 0|| eng d
022 |a 0324-721X 
040 |a SZTE Egyetemi Kiadványok Repozitórium  |b hun 
041 |a eng 
100 1 |a Poranen Timo 
245 1 0 |a Two new approximation algorithms for the maximum planar subgraph problem  |h [elektronikus dokumentum] /  |c  Poranen Timo 
260 |c 2008 
300 |a 503-527 
490 0 |a Acta cybernetica  |v 18 No. 3 
520 3 |a The maximum planar subgraph problem (MPS) is defined as follows: given a graph G, find a largest planar subgraph of G. The problem is NP-hard and it has applications in graph drawing and resource location optimization. Călinescu et al. [J. Alg. 27, 269-302 (1998)] presented the first approximation algorithms for MPS with nontrivial performance ratios. Two algorithms were given, a simple algorithm which runs in linear time for bounded-degree graphs with a ratio 7/18 and a more complicated algorithm with a ratio 4/9. Both algorithms produce outerplanar subgraphs. In this article we present two new versions of the simpler algorithm. The first new algorithm still runs in the same time, produces outerplanar subgraphs, has at least the same performance ratio as the original algorithm, but in practice it finds larger planar subgraphs than the original algorithm. The second new algorithm has similar properties to the first algorithm, but it produces only planar subgraphs. We conjecture that the performance ratios of our algorithms are at least 4/9 for MPS. We experimentally compare the new algorithms against the original simple algorithm. We also apply the new algorithms for approximating the thickness and outerthickness of a graph. Experiments show that the new algorithms produce clearly better approximations than the original simple algorithm by Călinescu et al. 
650 4 |a Természettudományok 
650 4 |a Számítás- és információtudomány 
695 |a Számítástechnika, Kibernetika, Algoritmus 
856 4 0 |u http://acta.bibl.u-szeged.hu/12832/1/Poranen_2008_ActaCybernetica.pdf  |z Dokumentum-elérés