Eva Rotenberg works on algorithmic problems relating to graphs, strings, and geometry, and is particularly fascinated by dynamic graphs: problems of efficiently updating various information about a graph as it undergoes changes such as insertions and deletions of edges.
Eva is an associate professor at Technical University of Denmark, and will be spending a few days at MPI.
Based on joint work with: Aleksander B. G. Christiansen, Jacob Holm, Ivor van der Hoog, Krzysztof D. Nowicki, Chris Schwiegelshohn, and Carsten Thomassen
The arboricity α of a graph is the number of forests it takes to cover all its edges. Being asymptotically related to the graph's degeneracy and maximal subgraph density, arboricity is considered a good measure of the sparsity of a graph. Natural computational questions about arboricity include: computing the arboricity, obtaining a decomposition of the edges into few forests, and orienting the edges so that each vertex has only close to α out-edges.
In this talk, we will address these questions in the /dynamic/ setting, in which the graph is subject to arbitrary, adversarial insertions and deletions of edges. We will see how maintaining an orientation with few out-edges from each vertex leads to efficient dynamic algorithms for /matching/, /colouring/, and decomposing into O(α) forests;
And we will see how to efficiently balance the number of out-edges in an orientation of the dynamic graph, via an almost local reconciliation between neighbouring vertices.