Abstract
Unit disk graphs are the intersection graphs of equal sized circles in the plane.
In this paper, we consider the maximum independent set problems on unit disk graphs. When the given unit disk graph is defined on a slab whose width is k, we propose an algorithm for finding a maximum independent set in \(\mathrm{O}(n^{4\lceil 2k/ \sqrt{3}\rceil})\) time where n denotes the number of vertices. We also propose a (1 – 1/r)-approximation algorithm for the maximum independent set problems on a (general) unit disk graph whose time complexity is bounded by \(\mathrm{O}(rn^{4\lceil 2(r-1)/ \sqrt{3}\rceil})\).
We also propose an algorithm for fractional coloring problems on unit disk graphs. The fractional coloring problem is a continuous version of the ordinary (vertex) coloring problem. Our approach for the independent set problem implies a strongly polynomial time algorithm for the fractional coloring problem on unit disk graphs defined on a fixed width slab. We also propose a strongly polynomial time 2-approximation algorithm for fractional coloring problem on a (general) unit disk graph.
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
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and intractability of approximation problems. In: Proc. 33rd IEEE Symposium on Foundations of Computer Science, pp. 13–22 (1992)
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics 86, 165–177 (1990)
Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics 6, 243–254 (1983)
Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981)
Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976)
Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.S.: Simple heuristics for unit disk graphs. Networks 25, 59–68 (1995)
Tardos, E.: A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research 34, 250–256 (1986)
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. on Computing 6, 505–517 (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Matsui, T. (2000). Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds) Discrete and Computational Geometry. JCDCG 1998. Lecture Notes in Computer Science, vol 1763. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-46515-7_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-46515-7_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67181-7
Online ISBN: 978-3-540-46515-7
eBook Packages: Springer Book Archive