Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, November 17, 2020, 12:15 pm

Duration: 30 minutes

Location: Zoom: conference room

Speaker: Hung Hoang

Assistance and Interdiction Problems on Interval Graphs

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login