On the Clique problem in intersection graphs of ellipses
Ambühl C, Wagner U. 2002. On the Clique problem in intersection graphs of ellipses. Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 2518, 489–500.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Ambühl, Christoph;
Wagner, UliISTA 
Series Title
LNCS
Abstract
Intersection graphs of disks and of line segments, respectively, have been well studied, because of both, practical applications and theoretically interesting properties of these graphs. Despite partial results, the complexity status of the Clique problem for these two graph classes is still open. Here, we consider the Clique problem for intersection graphs of ellipses which in a sense, interpolate between disc and ellipses, and show that it is APX-hard in that case. Moreover, this holds even if for all ellipses, the ratio of the larger over the smaller radius is some prescribed number. To our knowledge, this is the first hardness result for the Clique problem in intersection graphs of objects with finite description complexity. We also describe a simple approximation algorithm for the case of ellipses for which the ratio of radii is bounded.
Publishing Year
Date Published
2002-01-01
Proceedings Title
Proceedings of the 13th International Symposium on Algorithms and Computation
Publisher
Springer
Volume
2518
Page
489 - 500
Conference
ISAAC: International Symposium on Algorithms and Computation
Conference Location
Vancouver, Canada
Conference Date
2002-11-21 – 2002-11-23
ISBN
IST-REx-ID
Cite this
Ambühl C, Wagner U. On the Clique problem in intersection graphs of ellipses. In: Proceedings of the 13th International Symposium on Algorithms and Computation. Vol 2518. Springer; 2002:489-500. doi:10.1007/3-540-36136-7_43
Ambühl, C., & Wagner, U. (2002). On the Clique problem in intersection graphs of ellipses. In Proceedings of the 13th International Symposium on Algorithms and Computation (Vol. 2518, pp. 489–500). Vancouver, Canada: Springer. https://doi.org/10.1007/3-540-36136-7_43
Ambühl, Christoph, and Uli Wagner. “On the Clique Problem in Intersection Graphs of Ellipses.” In Proceedings of the 13th International Symposium on Algorithms and Computation, 2518:489–500. Springer, 2002. https://doi.org/10.1007/3-540-36136-7_43.
C. Ambühl and U. Wagner, “On the Clique problem in intersection graphs of ellipses,” in Proceedings of the 13th International Symposium on Algorithms and Computation, Vancouver, Canada, 2002, vol. 2518, pp. 489–500.
Ambühl C, Wagner U. 2002. On the Clique problem in intersection graphs of ellipses. Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 2518, 489–500.
Ambühl, Christoph, and Uli Wagner. “On the Clique Problem in Intersection Graphs of Ellipses.” Proceedings of the 13th International Symposium on Algorithms and Computation, vol. 2518, Springer, 2002, pp. 489–500, doi:10.1007/3-540-36136-7_43.
Google Scholar
ISBN Search