论文标题
间隔图中最短的啤酒路径查询
Shortest Beer Path Queries in Interval Graphs
论文作者
论文摘要
我们的兴趣在于至少经过一个被称为啤酒顶点的顶点之一的顶点之间的路径。这样的路径称为啤酒路径，两个顶点之间的啤酒距离是最短啤酒路径的长度。 我们表明，我们可以使用$ 2N \ log n + o（n） + o（| b | \ log n）$ bits表示未加权的间隔图，其中$ | b | $是啤酒顶点的数量。此数据结构回答$ O（\ log^\ Varepsilon n）$的啤酒距离查询，对于任何常数的$ \ varepsilon> 0 $和$ o（\ log^\ varepsilon n + d）$的最短啤酒路径查询，其中$ d $是两个nodes之间的啤酒距离。我们还表明，可以使用$ 3N + o（n）$位来表示适当的间隔图，以支持$ o（f（n）\ log n）$ inω（n）$ inω（n）\ inω（1）$和$ o（d）$时间中的最短啤酒路径查询。所有这些结果也都有时间空间的权衡。 最后，我们证明，啤酒适当间隔图的信息理论下限非常接近我们结构的空间，即$ \ log（4+2 \ sqrt {3}）n -o（n）$（或约$ 2.9 n $）位。
Our interest is in paths between pairs of vertices that go through at least one of a subset of the vertices known as beer vertices. Such a path is called a beer path, and the beer distance between two vertices is the length of the shortest beer path. We show that we can represent unweighted interval graphs using $2n \log n + O(n) + O(|B|\log n)$ bits where $|B|$ is the number of beer vertices. This data structure answers beer distance queries in $O(\log^\varepsilon n)$ time for any constant $\varepsilon > 0$ and shortest beer path queries in $O(\log^\varepsilon n + d)$ time, where $d$ is the beer distance between the two nodes. We also show that proper interval graphs may be represented using $3n + o(n)$ bits to support beer distance queries in $O(f(n)\log n)$ time for any $f(n) \in ω(1)$ and shortest beer path queries in $O(d)$ time. All of these results also have time-space trade-offs. Lastly we show that the information theoretic lower bound for beer proper interval graphs is very close to the space of our structure, namely $\log(4+2\sqrt{3})n - o(n)$ (or about $ 2.9 n$) bits.
