Abstract
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.