On the Clique problem in intersection graphs of ellipses Conference Paper


Author(s): Ambühl, Christoph; Wagner, Uli
Title: On the Clique problem in intersection graphs of ellipses
Title Series: LNCS
Affiliation
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.
Keywords: Clique problems; Description complexity; Hardness result; Intersection graph; Line segment; Partial results; Two-graphs
Conference Title: ISAAC: International Symposium on Algorithms and Computation
Volume: 2518
Conference Dates: November 21-23, 2002
Conference Location: Vancouver, BC, Canada
ISBN: 978-3-662-48970-3
Publisher: Springer  
Date Published: 2002-01-01
Start Page: 489
End Page: 500
DOI: 10.1007/3-540-36136-7_43
Open access: no
IST Austria Authors
  1. Uli Wagner
    50 Wagner
Related IST Austria Work