Abstract: Today’s graph networks are complex, large and evolving. This necessitates the discovery of new graph algorithms and techniques which can be adapted to modern graphs. I will talk about my research, which is primarily concerned with designing algorithms for networks which are undergoing changes. I will focus on two problems: graph matching and edge coloring. Numerous practical applications have motivated the study of these classical graph problems in evolving graphs. 

The problem of computing matchings on unweighted graphs in new models has received much attention. A natural generalization of this problem is the weighted setting, where edges have weights or cost functions. Unfortunately, there is a gap between the state-of-the-art for these two problems. In the first part of the talk, I will present a versatile framework which reduces the weighted setting to the unweighted setting. 

In the second part of the talk, I will present my work on edge coloring, where my focus has been on analyzing a particular natural and simple algorithm that is conjectured to be optimal. 

About the Speaker: I am a postdoc in the Big Data Algorithms Group at the University of Salzburg. Before this, I was a PhD student in the Computer Science Department of Rutgers University. My research interests are in graph algorithms.

We look forward your active participation.