Gräf, A., Stumpf, M., Weisenfels, G.: On coloring unit disk graphs. 671–679 (2001)įiala, J., Fishkin, A.V., Fomin, F.: Off-line and on-line distance constrained labeling of disk graphs. In: Proceedings the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), Washington, DC, January 7-9, pp.
Computational Geometry: Theory and Applications 23(2), 243–255 (2002)Įrlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric graphs. Discrete Mathematics 86, 165–177 (1990)Įrlebach, T., Fiala, J.: Independence and coloring problems on intersection graphs of disks (2001) (manuscript)Įrlebach, T., Fiala, J.: On-line coloring of geometric intersection graphs. Computational Geometry: Theory and Applications 9, 3–24 (1998)Ĭlark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. PhD thesis, University of british Columbia (1996)īreu, H., Kirkpatrick, D.G.: Unit disc graph recognition is NP-hard.
Journal of the ACM 41, 153–180 (1994)īreu, H.: Algorithmic Aspects of constrained unit disk graphs. In: Proceedings 15th Annual ACM-SIAM Symposium on Discrete Algorithms (2004) (to appear)īaker, B.S.: Approximation algorithms for np-complete problems on planar graphs. Agarwal, P.K., Overmars, M., Sharir, M.: Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks.
0 kommentar(er)
