Structural Sparseness: Theory and Practice
- Speaker: Dr Felix Reidl, Department of Computer Science and Information Systems, Birkbeck, University of London
- Date: Tuesday, 16 October 2018 from 17:00 to 18:00
- Location: Room 151
Sparseness is undoubtedly one of the most useful graph properties
for algorithm design: whether it is planarity for approximation schemes,
bounded treewidth for dynamic programming, or excluded minors for parametrised
algorithms. But do these algorithms actually translate into usable programs or
are they simply 'galactic algorithms' of theoretical interest only?
In this talk I invite you to critically examine the issue of practicality and
argue why theoreticians should care about it. I will particularly focus
on bounded expansion/nowhere dense classes and try to convince you that a
practical algorithmic toolkit exploiting those properties is feasible. Along
the way, I will highlight some of my recent experiences in the intersection of
practical algorithms and structural sparseness.