Better Approximation Schemes for Disk Graphs
| Autor: | Leeuwen, Erik Jan, Arge, L., Freivalds, R. |
|---|---|
| Přispěvatelé: | Networks and Optimization |
| Rok vydání: | 2006 |
| Předmět: |
Vertex cover
Computer Science::Computational Geometry 1-planar graph Metric dimension Planar graph Combinatorics Indifference graph symbols.namesake Chordal graph TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Independent set Data_FILES symbols Maximal independent set Astrophysics::Earth and Planetary Astrophysics Computer Science::Data Structures and Algorithms Astrophysics::Galaxy Astrophysics MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Algorithm Theory – SWAT 2006 ISBN: 9783540357537 SWAT Algorithm Theory-SWAT 2006 : 10th Scandinavian Workshop, Riga, Latvia, July 6-8, 2006 : proceedings, 316-327 STARTPAGE=316;ENDPAGE=327;TITLE=Algorithm Theory-SWAT 2006 : 10th Scandinavian Workshop, Riga, Latvia, July 6-8, 2006 : proceedings |
| DOI: | 10.1007/11785293_30 |
| Popis: | We consider Maximum Independent Set and Minimum Vertex Cover on disk graphs. We propose an asymptotic FPTAS for Minimum Vertex Cover on disk graphs of bounded ply. This scheme can be extended to an EPTAS on arbitrary disk graphs, improving on the previously known PTAS [8]. We introduce the notion of level density for disk graphs, which is a generalization of the notion of ply. We give an asymptotic FPTAS for Maximum Independent Set on disk graphs of bounded level density, which is also a PTAS on arbitrary disk graphs. The schemes are a geometric generalization of Baker’s EPTASs for planar graphs [3]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|