 |
Center for Nonlinear Studies |
It is generally agreed upon that real world networks are "sparse" (as defined by the ratio of vertices to edges), but this characterization is far from sufficient for designing efficient algorithms for analysis. This talk will discuss additional classes in the sparse graph hierarchy, focusing on bounded degeneracy and bounded expansion. We present new results characterizing whether several well-studied random graph models generate graphs satisfying these stronger sparsity conditions. We also describe fast, parameterized algorithms for counting induced subgraphs (and homomorphisms), and computing localized versions of several centrality measures in graph classes of bounded expansion.
We conclude by discussing several challenges and open problems. This includes joint work with A. Chin, E. Demaine, M. Farrell, T. Goodrich, N. Lemons, F. Reidl, P. Rossmanith, F. Sanchez Villamil, and S. Sikdar.
Host: Nathan Lemons