Abstract
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].
This research was supported by the Bsik project BRICKS.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P.K., Overmars, M., Sharir, M.: Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks. In: SODA 2004, pp. 516–525. SIAM, Philadelphia (2004)
Alber, J., Fiala, J.: Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs. J. Algorithms 52(2), 134–151 (2003)
Baker, B.S.: Approximation Algorithms for NP-Complete Problems on Planar Graphs. J. ACM 41(1), 153–180 (1994)
Chan, T.M.: Polynomial-time Approximation Schemes for Packing and Piercing Fat Objects. J. Algorithms 46(2), 178–189 (2003)
Chan, T.M.: A Note on Maximum Independent Sets in Rectangle Intersection Graphs. Inf. Proc. Let. 89(1), 19–23 (2004)
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit Disk Graphs. Discr. Math. 86(1–3), 165–177 (1990)
Eppstein, D., Miller, G.L., Teng, S.-H.: A Deterministic Linear Time Algorithm for Geometric Separators and its Applications. Fund. Inform. 22(4), 309–329 (1995)
Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time Approximation Schemes for Geometric Intersection Graphs. SIAM J. Computing 34(6), 1302–1323 (2005)
Hochbaum, D.S., Maass, W.: Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. J. ACM 32(1), 130–136 (1985)
Hunt III, D.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs. J. Algorithms 26(2), 238–274 (1998)
Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. Ver. Sächs. Ak. Wiss. Leipzig, Math.-Phys. Kl. 88, 141–164 (1936)
Malesińska, E.: Graph-Theoretical Models for Frequency Assignment Problems, PhD Thesis, Technical University of Berlin, Berlin (1997)
Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Networks 25, 59–68 (1995)
Marx, D.: Efficient Approximation Schemes for Geometric Problems? In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 448–459. Springer, Heidelberg (2005)
Matsui, T.: Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol. 1763, pp. 194–200. Springer, Heidelberg (2000)
Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.A.: Separators for Sphere-Packings and Nearest Neighbor Graphs. J. ACM 44(1), 1–29 (1997)
Nieberg, T., Hurink, J.L., Kern, W.: A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 214–221. Springer, Heidelberg (2004)
Robertson, N., Seymour, P.D.: Graph Minors. I. Excluding a Forest. J. Comb. Th. B 35, 39–61 (1983)
Telle, J.A., Proskurowski, A.: Algorithms for Vertex Partitioning Problems on Partial k-Trees. SIAM J. Disc. Math. 10(4), 529–550 (1997)
van Leeuwen, E.J.: Optimization Problems on Mobile Ad Hoc Networks – Algorithms for Disk Graphs, Master’s Thesis INF/SCR-04-32, Inst. of Information and Computing Sciences, Utrecht Univ. (2004)
van Leeuwen, E.J.: Approximation Algorithms for Unit Disk Graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 351–361. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Leeuwen, E.J. (2006). Better Approximation Schemes for Disk Graphs. In: Arge, L., Freivalds, R. (eds) Algorithm Theory – SWAT 2006. SWAT 2006. Lecture Notes in Computer Science, vol 4059. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11785293_30
Download citation
DOI: https://doi.org/10.1007/11785293_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35753-7
Online ISBN: 978-3-540-35755-1
eBook Packages: Computer ScienceComputer Science (R0)