- Series
- School of Mathematics Colloquium
- Time
- Thursday, September 20, 2018 - 11:00am for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Blair Sullivan – Department of Computer Science, NC State University
- Organizer
- Christine Heitsch
Techniques from structural graph theory hold significant promise for
designing efficient algorithms for network science. However, their
real-world application has been hampered by the challenges of unrealistic
structural assumptions, hidden costs in big-O notation, and
non-constructive proofs. In this talk, I will survey recent results which
address many of these concerns through an algorithmic pipeline for
structurally sparse networks, highlighting the crucial role of certain
graph colorings, along with several open problems. For example, we give
empirical and model-based evidence that real-world networks exhibit a form
of structural sparsity known as "bounded expansion,'' and discuss
properties of several low-treedepth colorings used in efficient algorithms
for this class.
Based on joint works with E. Demaine, J. Kun, M. O'Brien, M. Pilipczuk, F.
Reidl, P. Rossmanith, F. Sanchez Villaamil, and S. Sikdar.