A Centralized Local Algorithm for the Sparse Spanning Graph Problem
A Centralized Local Algorithm for the Sparse Spanning Graph Problem
复制标题
稀疏生成图问题的集中局部算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Reut Levi
中科院分区：
文献类型：
--
作者：
C. Lenzen;Reut Levi
构建稀疏跨度子图是图理论中的基本原始性。在本文中，我们在集中式的本地模型中研究了这个问题，在该模型中，目的是通过仅检查输入的一小部分来确定边缘是否是跨越子图的一部分；但是，答案必须在全球范围内保持一致，并且独立于先前的查询。
不幸的是，最大稀疏的跨度子图，即跨越树，不能在此模型中有效地构造。因此，我们将最多包含（1+epsilon）n边缘的跨度子图定居（其中n是顶点的数量，而epsilon是给定的近似/稀疏参数）。我们达到了O〜（poly（delta/epsilon）n^{2/3}）的查询复杂性，其中三角洲是输入图的最大程度。我们的算法是第一个在任意有限度图上进行的算法。此外，我们实现了算法输出一个跨度伸展的子图的附加属性，即距离大约保留。对于每个已删除的边缘的概率很高，在连接其端点的输出中都有O（log n *（delta+log n）/epsilon）啤酒花的o路径。
Constructing a sparse spanning subgraph is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries.
Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most (1+epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). We achieve a query complexity of O~(poly(Delta/epsilon)n^{2/3}), where Delta is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary bounded degree graphs. Moreover, we achieve the additional property that our algorithm outputs a spanning subgraph of bounded stretch i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of O(log n * (Delta+log n)/epsilon) hops in the output that connects its endpoints.
在生成树附近建造，很少进行局部检查
影响因子：
1
作者：
Levi, Reut;Moshkovitz, Guy;Ron, Dana;Rubinfeld, Ronitt;Shapira, Asaf
通讯作者：
Shapira, Asaf
稀疏生成图的局部算法
影响因子：
1.1
作者：
Levi, Reut;Ron, Dana;Rubinfeld, Ronitt
通讯作者：
Rubinfeld, Ronitt