Sunday, June 4, 2006, 11:15-12:15
Room 309
--------------------------------------------------------------------------------
Liam Roditty
TAU
Title: Dynamic and Static Graph Algorithms
Abstract:
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.