Combinatorics Seminar – Oct 1, 2021

1 October 2021, 2:30 pm, Zoom

Speaker: Shahin Kamali (Manitoba, CS)
Title: Algorithms for Burning Graph Families

Abstract: Graph burning is a simple model for the spread of social influence in networks. The objective is to measure how quickly a “fire”, e.g., a piece of fake news, can be spread in a network. The burning process takes place in discrete rounds. In each round, a new fire breaks out at a vertex, while the old fires extend to their neighbours and burn them. A burning schedule selects where the new fire breaks out at each round, and the burning problem asks for a schedule that burns all vertices in a minimum number of rounds. In this talk, we review some recent algorithmic results for burning families of graphs that include graphs of bounded path-wdith, tree-width, pathlength, and certain families of dense graphs.