Séminaire de Combinatoire de Lyon à l'ENS

Computing cliques and independent sets in geometric graphs.

par Nicolas Bousquet

Europe/Paris
Amphi A (Site Monod)

Amphi A

Site Monod

Description

In this talk, we will study several types of intersection graphs (intersection of segments in the real line, of disks in the plane...etc...) and show that some geometric notions such as Helly properties or small separators can help us to derive efficient algorithm for maximum cliques (maximum size of a cluster) or independent set (pairwise not related objects).