BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:David Pike and Andrea Burgess (Memorial University of Newfoundland
  and University of New Brunswick Saint John)
DTSTART:20210803T160000Z
DTEND:20210803T170000Z
DTSTAMP:20260416T224653Z
UID:CCM2021/7
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/CCM2021/7/">
 The Firebreak problem</a>\nby David Pike and Andrea Burgess (Memorial Univ
 ersity of Newfoundland and University of New Brunswick Saint John) as part
  of Carleton Combinatorics Meeting 2021\n\n\nAbstract\nSuppose a network i
 s represented by a graph $G$.  A fire (or some sort of contagion) breaks o
 ut at a vertex.  Firefighters then respond by establishing a single firebr
 eak consisting of $k$ other vertices of $G$. The fire cannot burn or pass 
 through these $k$ protected vertices\; however\, the fire subsequently spr
 eads to all vertices it can reach without passing through the firebreak.  
 A natural question arises: how many vertices can be prevented from burning
 ?\n\nWe discuss how this problem came to our attention\, how the research 
 process evolved\, and how collaborators became engaged.  We also delve int
 o the scientific aspects of the problem\, with emphasis on computational c
 omplexity.  In general\, the associated decision problem is NP-complete\, 
 but it is solvable in polynomial time for certain graph classes.  In addit
 ion\, we will discuss potential applications.\n\nThis is joint work with K
 athleen Barnetson\, Jessica Enright\, Jared Howell and Brady Ryan.\n
LOCATION:https://researchseminars.org/talk/CCM2021/7/
END:VEVENT
END:VCALENDAR