Aleksander Bjørn Grodt Christiansen is visiting the research group from October 9 till October 20. He will talk about his work on Tuesday, October 17th.

Date and time: Tuesday, October 17, 2023, 1:00 p.m.
Room: HS T01
Title: “Efficiently Maintaining and Applying Dynamic Out-Orientations”
Speaker: Aleksander Bjørn Grodt Christiansen

Abstract: A bounded out-orientation is an orientation of the edges of a graph such that the maximum out-degree is bounded. Dynamically maintaining such orientations witha close to optimal bound on the out-degrees is an important sub-procedure in thecurrently fastest known algorithms for well-studied problems such as dynamic densest subgraph, dynamic maximal matching, and dynamic graph colouring. In this talk, we will show how to efficiently maintain such out-orientations in dynamic graphs, and how to apply them as sub-procedures to design efficient dynamic algorithms for densest subgraph and colouring. The talk is based on a combination of joint work with Chandra Chekuri, Jacob Holm, Ivor van der Hoog, Krzysztof Nowicki, Kent Quanrud, Eva Rotenberg, and Chris Schwiegelshohn.

About the speaker: Aleksander is a PhD student at the Technical University of Denmark, supervised by Eva Rotenberg. Before that, he did a masters in mathematics at the University of Cambridge and a bachelors at the Technical University of Denmark. He is interested in a wide range of algorithmic problems, and most of his research has focused on graph algorithms and, in particular, dynamic graph algorithms. Other interests include combinatorics, combinatorial optimisation, and distributed algorithms.