Computing Parameters of Sequence-Based Dynamic Graphs

摘要

We present a general framework for computing parameters of dynamic networks which are modelled as a sequence G=(G1,G2,...,G) of static graphs such that Gi=(V,Ei) represents the network topology at time i and changes between consecutive static graphs are arbitrary. The framework operates at a high level, manipulating the graphs in the sequence as atomic elements with two types of operations: a composition operation and a test operation. The framework allows us to compute different parameters of dynamic graphs using a common high-level strategy by using composition and test operations that are specific to the parameter. The resulting algorithms are optimal in the sense that they use only O() composition and test operations, where is the length of the sequence. We illustrate our framework with three minimization problems, bounded realization of the footprint, temporal diameter, and round trip temporal diameter, and with T-interval connectivity which is a maximization problem. We prove that the problems are in NC by presenting polylogarithmic-time parallel versions of the algorithms. Finally, we show that the algorithms can operate online with amortized complexity (1) composition and test operations for each graph in the sequence.