论文标题
最佳顶点连通性甲环
Optimal Vertex Connectivity Oracles
论文作者
论文摘要
A $ K $ -VERTEX连接性甲骨文的无向$ G $是一种数据结构，在V（G）$中给定$ u，v \，报告$ \ min \ {k，κ（u，v）$，其中$κ（u，v）$是$ us u，v $ u，v $之间的$κ（u，v）$。效率的主要措施有三种：施工时间，查询时间和空间。 Izsak和Nutov的先前工作表明，总尺寸$ \ tilde {o}（kn）$的数据结构甚至可以被编码为$ \ tilde {o}（k）$ - 位标记方案，以便可以在$ \ tilde {o}（o}（k）$时。施工时间是多项式的，但未指定。 在本文中，我们介绍了前三个复杂性措施：空间，查询时间和施工时间。我们在任何顶点连接性甲骨文上给出$ω（kn）$ - 位下限。我们在最大流动时间构建了最佳空间连接性甲骨文，该甲骨文在$ o（\ log n）$时间中回答查询，独立于$ k $。
A $k$-vertex connectivity oracle for undirected $G$ is a data structure that, given $u,v\in V(G)$, reports $\min\{k,κ(u,v)\}$, where $κ(u,v)$ is the pairwise vertex connectivity between $u,v$. There are three main measures of efficiency: construction time, query time, and space. Prior work of Izsak and Nutov shows that a data structure of total size $\tilde{O}(kn)$ can even be encoded as a $\tilde{O}(k)$-bit labeling scheme so that vertex-connectivity queries can be answered in $\tilde{O}(k)$ time. The construction time is polynomial, but unspecified. In this paper we address the top three complexity measures: Space, Query Time, and Construction Time. We give an $Ω(kn)$-bit lower bound on any vertex connectivity oracle. We construct an optimal-space connectivity oracle in max-flow time that answers queries in $O(\log n)$ time, independent of $k$.
