Algorithmic graph theory

11/10/2019, 14:00 - 15:00 in MAP/0G/017

Munaro, Andrea (Queen’s University Belfast)


Abstract:

I will provide a short introduction to this field by presenting some of the most common problems and the way they are typically addressed. I will start from the observation that many algorithmic graph problems remain “hard” even for restricted classes of graphs, while they become “easy” for structured subclasses, and I will try to answer the following questions: Which structural properties of the instances guarantee efficient solvability? Can we identify a boundary separating “hard” and “easy” instances?

Mathematical Sciences Research Centre