Campus Event Calendar
Event Entry
What and Who
Algorithms for Firefighting
Erik Jan van Leeuwen
University of Rome “La Sapienza”
Lecture
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 13 March 2012
13:30
30 Minutes
E1 4
024
Saarbrücken
Abstract
Playing with fire is never a good idea, but in this talk we will study such a game regardless. A fire breaks out at a vertex of a graph, and in each time step the fire spreads to all of its neighbors. However, also in each time step, the fire brigade
is allowed to place one firefighter on a vertex of the graph in order to hose that vertex with water, thus preventing it from ever catching fire. The goal of this 'game' is to contain the fire while preventing a maximum number of vertices of the graph from catching fire.
We investigate this problem from a complexity point of view. The starting point of this investigation is the fact that the problem is NP-complete on trees. We then answer two of your most burning questions:
1) Is the problem fixed-parameter tractable and does it have a polynomial kernel?
2) Does the NP-completeness on trees mean that the problem is NP-complete on all sensible graph classes?
Contact
Danny Hermelin
--email hidden
passcode not visible
logged in users only
Danny Hermelin, 03/12/2012 17:48
Danny Hermelin, 03/12/2012 17:48 -- Created document.
Danny Hermelin, 03/12/2012 17:48 -- Created document.