The Clique Problem in Intersection Graphs of Ellipses and Triangles
The Clique Problem in Intersection Graphs of Ellipses and Triangles
复制标题
椭圆与三角形交图中的派系问题
DOI：
--
复制
发表时间：
2005
影响因子：
0.5
通讯作者：
Uli Wagner
中科院分区：
文献类型：
--
作者：
Christoph Ambühl;Uli Wagner
分别用圆盘和线段的交线图，
已经得到了很好的研究，因为实际应用和
这些图的理论上有趣的性质。尽管部分
结果，团问题的复杂性状况，
这两个图形类仍然是开放的。
在这里，我们考虑交图的团问题，
椭圆，在某种意义上，插在磁盘和线段之间，
这表明在这种情况下问题是APX困难的。而且这
即使对于所有椭圆，大椭圆与小椭圆的比率
半径是一个规定的数字。此外，立即减少
可以推广到三角形的交集图。
据我们所知，这是第一个硬度结果
有限凸体交图的团问题
描述复杂度我们还描述了一个简单的近似
算法的情况下，椭圆的半径比是
有界
AbstractIntersection 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.