Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/s00224-005-1141-6 | Theory Comput. Syst. |
Keywords | Field | DocType |
Computational Mathematic,Line Segment,Approximation Algorithm,Interesting Property,Simple Approximation | Discrete mathematics,Block graph,Combinatorics,Indifference graph,Clique-sum,Chordal graph,Treewidth,Trapezoid graph,Mathematics,Clique problem,Split graph | Journal |
Volume | Issue | ISSN |
38 | 3 | 1432-4350 |
Citations | PageRank | References |
9 | 0.56 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |
| Uli Wagner | 2 | 259 | 31.51 |