Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 17, 2022, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Nicolas Grelier
In this talk, I will present several nice results about maximum clique in disk graphs and related classes. First, I will present a polynomial time algorithm for unit disk graphs discovered by Clark, Colbourn and Johnson (‘90). I will also present an EPTAS for maximum clique in disk graphs as shown by Bonnet et al. (‘17) and Bonamy et al. (‘18).
One of the key ingredients used in the EPTAS is the fact that in disk graphs, the complement of two mutually induced odd cycles is a forbidden subgraph. Similarly, Atminas and Zamaraev (‘16) showed that in unit disk graphs, the complement of an edge and an odd cycle that are mutually induced is a forbidden subgraph. This leads to the study of maximum independent set in graphs where two mutually induced odd cycles, respectively one edge and an odd cycle, are forbidden subgraphs. I will present some results from an ongoing work together with Bonnet, Chakraborty and Thomassé.
Automatic MiSe System Software Version 1.4803M | admin login