Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 16, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Nicolas Grelier
We show that the strong chromatic index of unit disk graphs is efficiently 6-approximable. This improves on 8-approximability as shown by Barrett, Istrate, Kumar, Marathe, Thite, and Thulasidasan (2006). We also show that strong edge-6-colourability is NP-complete for the class of unit disk graphs. Thus there is no polynomial-time (7/6 − ε)-approximation unless P=NP.
Automatic MiSe System Software Version 1.4803M | admin login