The workshop will take place on August 16th in McDougall Hall 246 on the UPEI campus, beginning at 10am. An overview of the topic will be provided by Dr. Enright, after which students will work on open problems. This session is open to both graduate students and senior undergraduates. There is no registration fee. The workshop is presented by the AARMS Graph Searching in Atlantic Canada Collaborative Research Group.
Please confirm your attendance by Friday, July 22, 2022 by emailing Shannon Fitzpatrick (sfitzpatrick@upei.ca ) with the subject line Graph Searching Workshop Registration including the following information.
Name
University
Supervisor
If you require travel support please click here.
Starting with firefighter, we'll talk about spreading games on graphs and then focus in on dynamic or temporal graphs. A temporal graph is one in which the edges are assigned time steps and they are only active at those time steps - thus they can model data-derived contact networks that change over time. In Temporal Firefighter a fire breaks out at a specified vertex and spreads over active edges adjacent to a fire at each time step. We can (permanently) defend some budgeted number of vertices at each time step, and protected vertices stay protected forever, burning vertices burn forever. We can then ask questions about what proportion or number of vertices we can save.
Some things are known, and we will discuss existing results (e.g. a decision version of Temporal Firefighter is NP-Hard). We will look at open questions about algorithms, extremal graphs, and game variants. Time and interest permitting, we may consider other spreading games as well.