English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Intersection graphs of disks and of line segments, respectively,have been well studied, because of both practical applications andtheoretically interesting properties of these graphs. Despite partialresults, the complexity status of the Clique problem forthese two graph classes is still open.Here, we consider the Clique problem for intersection graphs ofellipses, which, in a sense, interpolate between disks and line segments, andshow that the problem is APX-hard in that case. Moreover, thisholds even if for all ellipses, the ratio of the larger over the smallerradius is some prescribed number. Furthermore, the reduction immediatelycarries over to intersection graphs of triangles.To our knowledge, this is the first hardness result for theClique problem in intersection graphs of convex objects with finitedescription complexity. We also describe a simple approximationalgorithm for the case of ellipses for which the ratio of radii isbounded.

The Clique Problem in Intersection Graphs of Ellipses and Triangles