Planar diameter via metric compression
Planar diameter via metric compression
复制标题
通过公制压缩获得的平面直径
DOI：
10.1145/3313276.3316358
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Parter
中科院分区：
文献类型：
--
作者：
Jason Li;M. Parter
我们针对平面图中的分布式距离计算开发了一种新方法，该方法基于Abboud等人[SODA’18]最近引入的度量压缩问题的一个变体。在我们的平面图度量压缩问题变体中，给定一个具有\(n\)个顶点的平面图\(G=(V,E)\)，一组位于单个面上的源端点\(S\subseteq V\)，以及一组目标端点\(T\subseteq V\)。目标是对\(S\times T\)距离进行紧凑编码。我们的一个关键技术贡献是提供了一种压缩方案，对于直径为\(D\)的无权图，使用\(O(|S|\cdot(D)+|T|)\)位对所有\(S\times T\)距离进行编码。这显著改进了\(O(|S|\cdot 2^{D}+|T|\cdot D)\)位的现有技术水平。我们还考虑了加权图问题的一个近似版本，其中对于给定的输入参数\(\epsilon\in(0,1]\)，目标是对\(S\times T\)距离的\((1 + \epsilon)\)近似进行编码。在这里，我们的压缩方案使用\(O((|S|/\epsilon)+|T|)\)位。此外，我们描述了如何在近线性时间内计算这些压缩方案。这种紧凑压缩方案的核心是基于平面图的VC - 维类型论证，使用了著名的Sauer引理。这种高效的压缩方案在直径计算设置中带来了一些改进和简化，特别是在分布式设置中：存在一个以高概率在\(O(D^{5})\)轮内计算平面图直径的随机分布式算法。对于加权平面图（无权直径为\(D\)），存在一个以高概率在\(O(D^{3})+D^{2}(\log n /\epsilon)\)轮内计算直径的\((1 + \epsilon)\)近似的随机分布式算法。在此之前，对于这些问题没有已知的亚线性轮算法。这些分布式构造基于一种新的递归图分解，该分解将每个子图的（无权）直径保持在一个对数项内。利用这种分解，我们还在\(O(D^{2})\)轮内得到了精确的单源最短路径树计算。
We develop a new approach for distributed distance computation in planar graphs that is based on a variant of the metric compression problem recently introduced by Abboud et al. [SODA’18]. In our variant of the Planar Graph Metric Compression Problem, one is given an n-vertex planar graph G=(V,E), a set of S ⊆ V source terminals lying on a single face, and a subset of target terminals T ⊆ V. The goal is to compactly encode the S× T distances. One of our key technical contributions is in providing a compression scheme that encodes all S × T distances using O(|S|·(D)+|T|) bits, for unweighted graphs with diameter D. This significantly improves the state of the art of O(|S|· 2D+|T| · D) bits. We also consider an approximate version of the problem for weighted graphs, where the goal is to encode (1+є) approximation of the S × T distances, for a given input parameter є ∈ (0,1]. Here, our compression scheme uses O((|S|/є)+|T|) bits. In addition, we describe how these compression schemes can be computed in near-linear time. At the heart of this compact compression scheme lies a VC-dimension type argument on planar graphs, using the well-known Sauer’’s lemma. This efficient compression scheme leads to several improvements and simplifications in the setting of diameter computation, most notably in the distributed setting: There is an O(D5)-round randomized distributed algorithm for computing the diameter in planar graphs, w.h.p. There is an O(D3)+D2(logn/є)-round randomized distributed algorithm for computing a (1+є) approximation for the diameter in weighted planar graphs, with unweighted diameter D, w.h.p. No sublinear round algorithms were known for these problems before. These distributed constructions are based on a new recursive graph decomposition that preserves the (unweighted) diameter of each of the subgraphs up to a logarithmic term. Using this decomposition, we also get an exact SSSP tree computation within O(D2) rounds.
登录
查看更多内容
轮次和消息最优分布式图算法
DOI：
10.1145/3212734.3212737
发表时间：
2018
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Haeupler, Bernhard;Hershkowitz, D. Ellis;Wajc, David
通讯作者：
Wajc, David
少数被排除在外的网络家族承认快速分布式算法
DOI：
10.1145/3212734.3212776
发表时间：
2018
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Haeupler, Bernhard;Li, Jason;Zuzic, Goran
通讯作者：
Zuzic, Goran
平面图中更快的近似直径和距离预言
影响因子：
1.1
作者：
Chan, Timothy M.;Skrepetos, Dimitrios
通讯作者：
Skrepetos, Dimitrios
通过快捷方式更快地进行分布式最短路径近似
DOI：
10.4230/lipics.disc.2018.33
发表时间：
2018
期刊：
International Symposium on Distributed Computing
影响因子：
--
作者：
Haeupler, Bernhard;Li, Jason
通讯作者：
Li, Jason
无需嵌入的低拥塞快捷方式
影响因子：
1.3
作者：
Haeupler, Bernhard;Izumi, Taisuke;Zuzic, Goran
通讯作者：
Zuzic, Goran