Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 17, 2020, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Hung Hoang
In this talk, I will talk about a novel framework of graph modifications specific to interval graphs. Using the framework, we study interdiction problems with respect to these graph modifications and the contrary to these problems, which we call assistance problems. Given a list of original intervals, each interval has a replacement interval such that either the replacement contains the original, or the original contains the replacement. The interdictor/assistant is allowed to replace up to k original intervals with their replacements. We study these problems for the independence number, the clique number, shortest paths, and Hamiltonicity, and obtain polynomial time algorithms based on dynamic programming for most of the studied problems.
This is joint work with Stefan Lendl and Lasse Wulf.
Automatic MiSe System Software Version 1.4803M | admin login