Fast and Simple Connectivity in Graph Timelines

DOI10.1007/978-3-319-21840-3_38MaRDI QIDQ3449843zbMATH OpenOpenAlexFDO

Authors Adam Karczmarz, Jakub Łącki

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.02973

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05)

Abstract: In this paper we study the problem of answering connectivity queries about a emph{graph timeline}. A graph timeline is a sequence of undirected graphs $G_1,ldots,G_t$ on a common set of vertices of size $n$ such that each graph is obtained from the previous one by an addition or a deletion of a single edge. We present data structures, which preprocess the timeline and can answer the following queries: - forall$(u,v,a,b)$ -- does the path $uov$ exist in each of $G_a,ldots,G_b$? - exists$(u,v,a,b)$ -- does the path $uov$ exist in any of $G_a,ldots,G_b$? - forall2$(u,v,a,b)$ -- do there exist two edge-disjoint paths connecting $u$ and $v$ in each of $G_a,ldots,G_b$ We show data structures that can answer forall and forall2 queries in $O(logn)$ time after preprocessing in $O(m+tlogn)$ time. Here by $m$ we denote the number of edges that remain unchanged in each graph of the timeline. For the case of exists queries, we show how to extend an existing data structure to obtain a preprocessing/query trade-off of $langleO(m+min(nt,t^{2-alpha})),O(t^{a}lpha)angle$ and show a matching conditional lower bound.

Recommendations

• Faster exploration of degree-bounded temporal graphs
• Reachability in graph timelines
• On short fastest paths in temporal graphs
• Efficient temporal core maintenance of massive graphs
• scientific article; zbMATH DE number 2080092
• Time windowed data structures for graphs
• Algorithms for Extracting Timeliness Graphs

Cited in

(7)

• Conditional lower bounds for dynamic geometric measure problems
• Conditional lower bounds for dynamic geometric measure problems
• Algorithms for Extracting Timeliness Graphs
• Engineering Time-Expanded Graphs for Faster Timetable Information
• How fast can we play Tetris greedily with rectangular pieces?
• Reachability in graph timelines
• Deterministic 3SUM-hardness

This page was built for publication: Fast and Simple Connectivity in Graph Timelines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449843)