%0 Conference Paper %1 lacki2013reachability %A Lacki, Jakub %A Sankowski, Piotr %B Proceedings of the 4th Conference on Innovations in Theoretical Computer Science %C New York, NY, USA %D 2013 %I ACM %K algorithms connectivity dynamic_graphs graph_algorithms graph_theory %P 257--268 %R 10.1145/2422436.2422468 %T Reachability in Graph Timelines %U http://doi.acm.org/10.1145/2422436.2422468 %X In this paper we consider the problem of maintaining information about graphs with history -- so called graph timeline. A graph timeline is a sequence of graphs G1,..., Gt, in which consecutive graphs are obtained from previous ones by small modifications, e.g., by adding or removing a single edge. We aim to devise algorithms that after some preprocessing are able to efficiently answer queries about the existence of paths in the entire timeline of the graph, or within some time interval. We consider two types of queries: forall (u,v,a,b) --- query that checks if there exists a path from u to v in each of Ga,..., Gb; exists(u,v,a,b) --- query that checks if there exists a path from u to v in any of Ga,...,Gb. Our study is motivated by the recent intensive study of the evolution of graphs, and the question whether information about history can be efficiently aggregated. We show that for path queries this is, somewhat astonishingly, true. In some cases it is possible to preprocess graph timeline and answer such queries in almost optimal time. First, we consider undirected graphs and timelines in which two consecutive graphs differ by addition or removal of a single edge. We show a randomized algorithm that requires O(t log t log log t log n+m) preprocessing time and answers forall queries in O(log n log log t) time. Here, $n$ is the number of vertices in the graph and m is the number of permanent edges, that is edges common to all graphs in the timeline. This algorithm can be derandomized at some cost in the running time. Second, we give a deterministic algorithm that needs O(nt+m) preprocessing and answers exists queries in O(1) time. Finally, for directed graphs, we consider timelines where two consecutive graphs differ by addition or removal of a set of edges incident to one vertex. In this case we, are able to propose a randomized algorithm that after O(nω-1t) preprocessing time can answer exists(u,v,a,b) queries in O(n) time and forall(u,v,a,b) queries in O(n+b-a) time. %@ 978-1-4503-1859-4

@inproceedings{lacki2013reachability, abstract = {In this paper we consider the problem of maintaining information about graphs with history -- so called graph timeline. A graph timeline is a sequence of graphs G1,..., Gt, in which consecutive graphs are obtained from previous ones by small modifications, e.g., by adding or removing a single edge. We aim to devise algorithms that after some preprocessing are able to efficiently answer queries about the existence of paths in the entire timeline of the graph, or within some time interval. We consider two types of queries: [forall (u,v,a,b)] --- query that checks if there exists a path from u to v in each of Ga,..., Gb; [exists(u,v,a,b)] --- query that checks if there exists a path from u to v in any of Ga,...,Gb. Our study is motivated by the recent intensive study of the evolution of graphs, and the question whether information about history can be efficiently aggregated. We show that for path queries this is, somewhat astonishingly, true. In some cases it is possible to preprocess graph timeline and answer such queries in almost optimal time. First, we consider undirected graphs and timelines in which two consecutive graphs differ by addition or removal of a single edge. We show a randomized algorithm that requires O(t log t log log t log n+m) preprocessing time and answers forall queries in O(log n log log t) time. Here, $n$ is the number of vertices in the graph and m is the number of permanent edges, that is edges common to all graphs in the timeline. This algorithm can be derandomized at some cost in the running time. Second, we give a deterministic algorithm that needs O(nt+m) preprocessing and answers exists queries in O(1) time. Finally, for directed graphs, we consider timelines where two consecutive graphs differ by addition or removal of a set of edges incident to one vertex. In this case we, are able to propose a randomized algorithm that after O(nω-1t) preprocessing time can answer exists(u,v,a,b) queries in O(n) time and forall(u,v,a,b) queries in O(n+b-a) time.}, acmid = {2422468}, added-at = {2019-09-12T19:32:20.000+0200}, address = {New York, NY, USA}, author = {Lacki, Jakub and Sankowski, Piotr}, biburl = {https://www.bibsonomy.org/bibtex/2c8e117f17338716333eefca7e0781324/peter.ralph}, booktitle = {Proceedings of the 4th Conference on Innovations in Theoretical Computer Science}, doi = {10.1145/2422436.2422468}, interhash = {17d078d1571a388f328a0868c2846605}, intrahash = {c8e117f17338716333eefca7e0781324}, isbn = {978-1-4503-1859-4}, keywords = {algorithms connectivity dynamic_graphs graph_algorithms graph_theory}, location = {Berkeley, California, USA}, numpages = {12}, pages = {257--268}, publisher = {ACM}, series = {ITCS '13}, timestamp = {2019-09-12T19:32:20.000+0200}, title = {Reachability in Graph Timelines}, url = {http://doi.acm.org/10.1145/2422436.2422468}, year = 2013 }