Fast and Simple Connectivity in Graph Timelines
Fast and Simple Connectivity in Graph Timelines
复制标题
图表时间线中快速、简单的连接
DOI：
10.1007/978-3-319-21840-3_38
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Jakub Lacki
中科院分区：
文献类型：
--
作者：
Adam Karczmarz;Jakub Lacki
在本文中，我们研究了回答有关\emph{图时间轴}的连接查询的问题。图时间线是一组大小为 $n$ 的公共顶点上的一系列无向图 $G_1,\ldots,G_t$，这样每个图都是通过添加或删除单个边从前一个图获得的。我们提出了数据结构，它对时间线进行预处理并可以回答以下查询：
- forall$(u,v,a,b)$ -- 路径 $u\to v$ 是否存在于每个 $G_a,\ldots,G_b$ 中？
- 存在$(u,v,a,b)$ -- 路径$u\to v$ 是否存在于$G_a,\ldots,G_b$ 中？
- forall2$(u,v,a,b)$ -- 在 $G_a,\ldots,G_b$ 中是否存在连接 $u$ 和 $v$ 的两条边不相交路径
我们展示了在 $O(m+t\log n)$ 时间内进行预处理后，可以在 $O(\log n)$ 时间内回答 forall 和 forall2 查询的数据结构。这里，$m$ 表示时间线的每个图中保持不变的边的数量。对于存在查询的情况，我们展示了如何扩展现有数据结构以获得 $\langle O(m+\min(nt, t^{2-\alpha})), O(t^\alpha)\rangle$ 的预处理/查询权衡，并显示匹配的条件下界。
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 $u\to v$ exist in each of $G_a,\ldots,G_b$?
- exists$(u,v,a,b)$ -- does the path $u\to v$ 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(\log n)$ time after preprocessing in $O(m+t\log n)$ 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 $\langle O(m+\min(nt, t^{2-\alpha})), O(t^\alpha)\rangle$ and show a matching conditional lower bound.