How to approach Dynamic graph related problems

Dynamic graph models have been studied intensively in distributed computing. For distributed algorithms, the computation is structured into rounds and the topology of graphs (=network) might undergo some changes from round to round, which are under control of an adversary. Moreover, every node of the graph runs an algorithm which can send a message to its (current!) neighbors. (This message is the input of the neighbors' algorithm in the next round.) What makes things interesting, is that a node does not "see" the entire graph but only its local neighborhood. Problems that are considered in these settings are for example information spreading where every node in the graph initially holds a token and eventually you want that every node has seen every token. The goal is to design algorithms that achieve this in the smallest number of rounds, using the least number of messages. See [2] for a recent survey. For the non-distributed setting, you might want to look at [1], which is an extension of the paper that you've mentioned. [1] Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal, Fabio Vandin: http://doi.acm.org/10.1145/2090236.2090249. ITCS 2012: 149-160 [2] Fabian Kuhn, Rotem Oshman: http://doi.acm.org/10.1145/1959045.1959064. SIGACT News 42(1): 82-96 (2011)

Building on @Peter answers (it is a very long comment, so I just included as an answer hopping that someone will benefit from it). I would suggest the following reference: Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: Time-varying graphs and dynamic networks. IJPEDS 27(5): 387-408 (2012) The survey includes a theoretical classification of dynamic networks in distributed settings. For instance, you may find graphs in which the appearance of edges follows a periodic pattern. Or, edges show up at least once in a period $\Delta$. Or, edges that do not follow any periodic patter but they will show up at some point of the algorithm execution. -- and there are about 9 classes in total. What is really important of this classification is that there are inclusion relationships between the different classes. So if you solve a problem in a certain class, you would solve it in every other class it is included in. The same authors presented broadcasting algorithms on some of the mentioned graphs. They gave different performance metrics related to time (i.e. different definition of shortest time). In broadcasting, the idea is that each node build a view of the network in the time domain. This is done by repeatedly listening to neighbors, and sending information to neighbors. If assuming periodicity, then a node can tell what is the shortest time-path to another node. It uses this information in routing. More details can be found in: Arnaud Casteigts, Paola Flocchini, Bernard Mans, Nicola Santoro: Deterministic Computations in Time-Varying Graphs: Broadcasting under Unstructured Mobility. IFIP TCS 2010: 111-124 One of the interesting concepts in dynamic graphs is the concept of journey, which has an analogy to path in static graphs. There is a journey between two nodes $u$ and $v$ if there is a set of edges $\{(u,x_1), (x_1, x _2), ...., (x _k, v)\}$ that will appear in an increasing intervals of time. Note that journey are not symmetric. The existence of a journey between $u$ and $v$ does not necessarily mean that there is a journey between $v$ and $u$. I attended a lecture by the previous authors. From my understanding, they claim that we are far from being able to deal with dynamic graph algorithms (following the definitions they follow). That we are still in the case of simple classes. In fact, they claim that most of the mobile computing algorithms just assume that their algorithms are too fast to be executed while the network is in transition ! (which i believe I heard a lot) -- Or simply, assume periodicity of edges appearance (see delay tolerant networks etc)