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.

AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

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.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

974 6298 9871

passcode not visible

logged in users only

If you wish to attend the talk online but do not have the password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.