Séminaire de Combinatoire de Lyon à l'ENS

Computing cliques and independent sets in geometric graphs.

by Nicolas Bousquet

Amphi A (Site Monod)

Amphi A

Site Monod


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).