Paper Info
Title
On the Clique Problem in Intersection Graphs of Ellipses
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.
Year
DOI
Venue
2002
10.1007/3-540-36136-7_43
ISAAC
Keywords
Field
DocType
finite description complexity,intersection graphs,clique problem,partial result,hardness result,practical application,line segment,graph class,prescribed number,complexity status,intersection graph
Block graph,Discrete mathematics,Combinatorics,Indifference graph,Clique-sum,Chordal graph,Treewidth,Trapezoid graph,Clique problem,Mathematics,Split graph
Conference
Volume
ISSN
ISBN
2518
0302-9743
3-540-00142-5
Citations 
PageRank 
References 
0
0.34
10
Authors
2
Name
Order
Citations
PageRank
Christoph Ambühl135718.50
Uli Wagner225931.51