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 <>
Submitted on : Tuesday, May 23, 2006 - 7:57:31 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 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

225

Files downloads

375