Fall 2013

Evolving Graphs

Thursday, November 21st, 2013 10:30 am10:55 am

Add to Calendar

We consider the following computational model on graphs that slowly change over time.  At each time step, the graph incurs a unit update and an algorithm has to periodically probe the graph to learn about the update and modify its solution accordingly.  We discuss algorithms in this model for basic graph questions including path connectivity, minimum spanning trees, and PageRank.