Linear Size Distance Preservers
Linear Size Distance Preservers
复制标题
线性尺寸距离保持器
DOI：
10.1137/1.9781611974782.39
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Gregory Bodwin
中科院分区：
文献类型：
--
作者：
Gregory Bodwin
在一个n节点图G中，p个节点对的距离集是在所有p个距离上都与G一致的子图。平凡的下界表明，最坏情况下的长度的距离boundaries至少是线性的在$n$和$p$;也就是说，$\Omega（n + p）$边有时需要在子图。在这项工作中，我们试图分类在什么情况下这是紧的，即在$O（n+p）$边缘上的距离保证存在。我们给出了三个相当简单的论点，使这个基本问题的新进展：
1.任何$p = O（n^{1/3}）$节点对在$O（n）$边上的距离为零（即使$G$是有向和加权的）。
2.当$G$是无向和无权的时，任何$p = \Omega\left（\frac{n^2}{rs（n）}\right）$节点对在$O（p）$边上的距离为零。这里，$rs（n）$是组合图论中的Ruzsa-Szemeredi函数。
3.我们有时需要$\omega（s^2）$边来保持$s = o（n^{2/3}）$节点子集内的所有成对距离，即使$G$是无向的。如果我们另外要求$G$是未加权的，那么范围福尔斯稍微下降到$s \le n^{2/3 - o（1）}$。
A distance preserver of $p$ node pairs in an $n$-node graph $G$ is a subgraph that agrees with $G$ on all $p$ of these distances. Trivial lower bounds show that the worst-case size of distance preservers is at least linear in $n$ and $p$; that is, $\Omega(n + p)$ edges are sometimes needed in the subgraph. In this work, we try to categorize in what situations this is tight, i.e. a distance preserver on $O(n+p)$ edges is guaranteed to exist. We give three fairly simple arguments that make new progress on this basic question:
1. Any $p = O(n^{1/3})$ node pairs have a distance preserver on $O(n)$ edges (even if $G$ is directed and weighted).
2. Any $p = \Omega\left(\frac{n^2}{rs(n)}\right)$ node pairs have a distance preserver on $O(p)$ edges when $G$ is undirected and unweighted. Here, $rs(n)$ is the Ruzsa-Szemeredi function from combinatorial graph theory.
3. We sometimes need $\omega(s^2)$ edges to preserve all pairwise distances within a subset of $s = o(n^{2/3})$ nodes, even if $G$ is undirected. If we additionally require that $G$ is unweighted, then the range falls slightly to $s \le n^{2/3 - o(1)}$.
一般图的线性大小对数拉伸路径报告距离预言机
影响因子：
1.3
作者：
Elkin, Michael;Pettie, Seth
通讯作者：
Pettie, Seth
更好的距离保持器和附加扳手
影响因子：
1.3
作者：
Bodwin, Greg;Williams, Virginia Vassilevska
通讯作者：
Williams, Virginia Vassilevska