Local Algorithms for Sparse Spanning Graphs
Local Algorithms for Sparse Spanning Graphs
复制标题
稀疏生成图的局部算法
DOI：
10.1007/s00453-019-00612-6
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
Rubinfeld, Ronitt
中科院分区：
文献类型：
--
作者：
Levi, Reut;Ron, Dana;Rubinfeld, Ronitt
构造图的生成树是图论中最基本的任务之一。我们在局部算法的设置中考虑这个问题的一个宽松版本。松弛的是，构造的子图是一个包含最多stedges（其中是顶点的数量，是给定的近似值/稀疏度参数）的parse生成子图。在局部设置中，目标是快速确定给定边是否属于这样的子图，而不是构造整个子图，而是通过检查（查询）e的局部邻域。挑战在于保持一致性。即根据同张子图给出关于不同边的答案。我们首先证明了对于一般的有界度图，任何这样的算法的查询复杂度必须为。这个下界适用于具有高展开式的常次图。接下来，我们设计了一个高展开式（有界度）图的算法，得到了一个与下界大致匹配的结果。然后，我们转而研究排除固定小项的图（因此是非展开的）。我们为这类图设计了一种算法，它可能具有无界的最大度。该算法的查询复杂度为（与最大度无关），其中为被排除次要点的顶点数。虽然我们的两种算法是为非常不同类型的图设计的（并且具有非常不同的复杂性），但在高层次上有一些相似之处，我们强调了相似之处和不同点。
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is asparse spanning subgraphcontaining at mostedges (wherenis the number of vertices andis a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edgeebelongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood ofe. The challenge is to maintain consistency. That is, to provide answers concerning different edges according to thesamespanning subgraph. We first show that for general bounded-degree graphs, the query complexity of any such algorithm must be. This lower bound holds for constant-degree graphs that have high expansion. Next we design an algorithm for (bounded-degree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence non-expanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is(independent ofnand the maximum degree), wherehis the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a high-level there are several similarities, and we highlight both the similarities and the differences.
登录
查看更多内容
在生成树附近建造，很少进行局部检查
影响因子：
1
作者：
Levi, Reut;Moshkovitz, Guy;Ron, Dana;Rubinfeld, Ronitt;Shapira, Asaf
通讯作者：
Shapira, Asaf
近似有界度和一般稀疏图中属性的距离
DOI：
10.1145/1497290.1497298
发表时间：
2009
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
S. Marko;D. Ron
通讯作者：
D. Ron
DOI：
10.1145/100216.100254
发表时间：
1990
期刊：
J. Parallel Distributed Comput.
影响因子：
--
作者：
N. Alon;P. Seymour;R. Thomas
通讯作者：
R. Thomas
DOI：
10.1007/978-3-642-22935-0_45
发表时间：
2011
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
A. Edelman;Avinatan Hassidim;H. N. Nguyen;Krzysztof Onak
通讯作者：
Krzysztof Onak
当地财产恢复
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
Zvika Brakerski
通讯作者：
Zvika Brakerski