HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

The clique number of unit quasi-disk graphs

Stephan Ceroi 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : For $\epsilon \in [0,1]$, a unit $\epsilon$-quasi-disk is a connected compact set $Q$ of the plane such that there exists a point $P$ such that $D(P,1-\epsilon) \subseteq Q \subseteq D(P,1)$, where $D(C,r)$ denotes the disk of centre $C$ and radius $r$. We prove that for any fixed $\epsilon>0$, the clique number problem on the class of intersection graphs of unit $\epsilon$-quasi-disks is NP-complete.
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072169
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:57:31 PM
Last modification on : Friday, February 4, 2022 - 3:19:54 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:56:44 PM

Identifiers

  • HAL Id : inria-00072169, version 1

Collections

Citation

Stephan Ceroi. The clique number of unit quasi-disk graphs. RR-4419, INRIA. 2002. ⟨inria-00072169⟩

Share

Metrics

Record views

77

Files downloads

150