Tel-Aviv University - Computer Science Colloquium

Sunday, June 4, 2006, 11:15-12:15

Room 309
Schreiber Building


Liam Roditty


Title: Dynamic and Static Graph Algorithms




In this talk I will survey some of the latest developments in dynamic

algorithms for fundamental graph problems such as connectivity (for

undirected graphs) and reachability (for directed graphs). In the last five years many

new algorithms for dynamic graphs problem were developed, some of them are

part of my PhD thesis. In the lecture I will describe an algorithm with an

almost linear update time for the reachability problem.