News Archives

Zombies, ETs and Other Encounters with Dynamic Graph Algorithms

November 16, 2007

  • Date: Friday, November 16th, 2007 
  • Time: 1 pm — 2:30 pm 
  • Place: ME 218

Valerie King 
University of Victoria

Abstract: Given any graph problem, we may ask if it’s possible to maintain a solution as an input graph changes incrementally, in time faster than recomputing from scratch for each update. The goal of a dynamic graph algorithm is to efficiently implement update and query operations in reasonable space.

This talk will be a whirlwind tour of fundamental ideas in dynamic graph algorithms and lower bounds, focusing mainly on the problems of connectivity and minimum spanning tree, transitive closure and shortest paths.

Bio: Valerie King is Professor in the Computer Science Department at the University of Victoria. She received her A.B. in mathematics from Princeton, her J.D. and Ph.D. from Boalt Hall and the Computer Science Dept. at UC Berkeley. She held post-doctoral positions at Princeton University and the University of Toronto. She has been a research scientist at NECI in Princeton, and at Compaq SRC and HP Labs. She was a visiting researcher at Microsoft Research Labs in Silicon Valley, a visiting professor at Hebrew University and the University of Copenhagen and a visiting scholar at UC Berkeley. She has been a member of the California Bar since 1981. She has done extensive work in dynamic graph algorithms, and is currently working on algorithms with applications to networks, computational biology, and distributed computing, as well as sociology of the web.