Campus Event Calendar

Event Entry

What and Who

Sparsity-adaptive dynamic graph algorithms

Eva Rotenberg
Technical University of Denmark
AG1 Mittagsseminar (own work)

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  
AG Audience

Date, Time and Location

Tuesday, 13 December 2022
60 Minutes
E1 4


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

Virtual Meeting Details

974 6298 9871
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the password, contact Roohani Sharma at

Roohani Sharma, 12/06/2022 19:14
Roohani Sharma, 11/29/2022 02:29
Roohani Sharma, 11/18/2022 12:01 -- Created document.