Talk, Univ. de Vest, Timisoara

This Friday, February 15, I am giving a talk at Timisoara, hosted by Gabriel Istrate. The talk is roughly an overview of the world of dynamic graph algorithms (no background assumed) --- what are the milestone results, the current research, and the big challenges for the future.

When it comes to current research, I will understandably be biased towards my own work, and will talk primarily about:

• how to generalize graph bridges to understand multiple edges going down (this paper with Mikkel Thorup). Big open problem: worst-case bounds.
• how to handle node failures, not just edge failures (this paper with Timothy Chan and Liam Roditty). Big open problem: handling node failures better and for more queries.

Formal details for those who want to attend:

Locatia: Universitatea de Vest. Sala 045C (Institutul e-Austria)
Ora: 10:00 am (vineri, 10 februarie)
Titlu: Algoritmi pentru grafuri dinamice
---
In multe aplicatii naturale, grafurile cu care avem de-a face au o structura dinamica: conexiunile (muchiile) dintr-o retea de calculatoare se pot strica sau repara; o configurare gresita sau un reboot poate scoate din folosinta un router (nod in graf); etc. Aceste cerinte au dus la un studiu intens al algoritmilor pe grafuri dinamice, care dureaza de peste 20 de ani si nu pare sa se apropie de sfarsit.

In aceasta prezentare, nu vom presupune cunostiinte anterioare despre grafuri dinamice, si vom incepe cu o introducere a domeniului. Apoi ne vom concentra pe cateva rezultate recente, si vom discuta multitudinea de probleme care raman inca nerezolvate.