DIKU Bits: Dynamic Graph Algorithms

Picture of event

On 24 May the Algorithms and Complexity (AC) Section at Department of Computer Science, University of Copenhagen, will give a DIKU Bits lecture.

Speaker 

Jacob Holm, Assistant professor, tenure track in the AC Section at Department of Computer Science, University of Copenhagen.

Title

Dynamic Graph Algorithms

Abstract

Graphs are a fundamental tool for structuring our knowledege of the world. Examples include road networks, computer networks, the social media graph, program flow graphs, neural networks, chemical bond graphs, etc. Many of the graphs we are interested in are "dynamic" i.e. they change over time, and as they change, so do their properties. I will sketch the main ideas behind our 2020 breakthrough result on how to maintain whether a dynamic graph can be drawn in the plane without crossing lines.

Which courses do you teach?: MSc I am currently teaching the Randomized Algorithms (RA) course, and will be co-teaching Advanced Algorithms and Data Structures (AADS) and Topics in Algorithms and Data Structures (TADS).

Which technology/research/projects/startup are you excited to see the evolution of? These past few years have seen some breakthrough results in the field of dynamic graph algorithms. Many of these results use the concept of an "expander decomposition" of a graph, and I believe that much more can be done using this tool.

What is your favorite sketch from the DIKUrevy?There are so many good ones it is hard to choose. Maybe "Jeg kender et sprog (2007)" or "Lad det gro (2014)". Or from really ancient times "Eksamenssangen" to the tune of Bohemian Rhapsody by Queen.