The Clique problem in intersection graphs of ellipses and triangles

C. Ambühl, U. Wagner, Theory of Computing Systems 38 (2005) 279–292.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Ambühl, Christoph; Wagner, UliIST Austria
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 disks and line segments, and show that the problem 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. Furthermore, the reduction immediately carries over to intersection graphs of triangles. To our knowledge, this is the first hardness result for the Clique problem in intersection graphs of convex 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
2005-05-01
Journal Title
Theory of Computing Systems
Volume
38
Issue
3
Page
279 - 292
IST-REx-ID

Cite this

Ambühl C, Wagner U. The Clique problem in intersection graphs of ellipses and triangles. Theory of Computing Systems. 2005;38(3):279-292. doi:10.1007/s00224-005-1141-6
Ambühl, C., & Wagner, U. (2005). The Clique problem in intersection graphs of ellipses and triangles. Theory of Computing Systems, 38(3), 279–292. https://doi.org/10.1007/s00224-005-1141-6
Ambühl, Christoph, and Uli Wagner. “The Clique Problem in Intersection Graphs of Ellipses and Triangles.” Theory of Computing Systems 38, no. 3 (2005): 279–92. https://doi.org/10.1007/s00224-005-1141-6.
C. Ambühl and U. Wagner, “The Clique problem in intersection graphs of ellipses and triangles,” Theory of Computing Systems, vol. 38, no. 3, pp. 279–292, 2005.
Ambühl C, Wagner U. 2005. The Clique problem in intersection graphs of ellipses and triangles. Theory of Computing Systems. 38(3), 279–292.
Ambühl, Christoph, and Uli Wagner. “The Clique Problem in Intersection Graphs of Ellipses and Triangles.” Theory of Computing Systems, vol. 38, no. 3, Springer, 2005, pp. 279–92, doi:10.1007/s00224-005-1141-6.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar