Distributed Strong Diameter Network Decomposition: Extended Abstract
Distributed Strong Diameter Network Decomposition: Extended Abstract
复制标题
分布式强直径网络分解：扩展摘要
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ofer Neiman
中科院分区：
文献类型：
--
作者：
Michael Elkin;Ofer Neiman
对于一对正参数 D,X，将 n 顶点图 G = (V,E) 的顶点集 V 划分为直径至多为 D 的不相交簇，称为 (D,X) 网络分解}，如果通过收缩 P 的每个簇获得的超图 G(P) 可以正确地进行 X 着色。如果每个簇的直径最大为 D，则分解 P 被称为强（或弱），即，如果对于每个簇 C ∈ P 且每两个顶点 u,v ∈ C，它们在 C 的导出图 G(C)（或在 G 中）中的距离至多为 D。网络分解是一种强大的构造，在分布式计算及其他领域非常有用。它是由 Awerbuch 等人提出的。等人。 [AGLP89] 八十年代末。这些作者表明，强 (2O(√log n log log n)、2O(√log n log log n) 网络分解可以在 2O(√log n log log n) 分布式时间内计算。他们的结果在九十年代初由 Panconesi 和 Srinivasan [PS92] 改进，他们表明所有三个表达式中的 2O(√log n 可以用 2O(√log n) 代替。大约在同一时间 Linial 和 Saks [LS93]设计了一种巧妙的随机算法，可以在 O(log2 n) 时间内构建弱 (O(log n),O(log n)) 网络分解。 n) 可以使用短消息在分布式 2o(√log n) 时间内构建，或者如果可以加强 [LS93] 的结果以在 O(log2 n) 时间内提供强 (O(log n),O(log n)) 网络分解（即使使用大消息）。在本文中，我们肯定地回答了这些长期存在的开放问题，并表明强 (O(log n),O(log n)) 网络分解可以在 O(log2 n) 时间内计算。我们的工作受到 Blelloch 等人 [BGKMPT11] 和 Miller 等人 [MPX13] 的启发并依赖于这种方法，我们将他们的方法应用于分布式计算模型。
For a pair of positive parameters D,Χ, a partition P of the vertex set V of an n-vertex graph G = (V,E) into disjoint clusters of diameter at most D each is called a (D,Χ) network decomposition}, if the supergraph G(P), obtained by contracting each of the clusters of P, can be properly Χ-colored. The decomposition P is said to be strong (resp., weak) if each of the clusters has strong (resp., weak) diameter at most D, i.e., if for every cluster C ∈ P and every two vertices u,v ∈ C, the distance between them in the induced graph G(C) of C (resp., in G) is at most D. Network decomposition is a powerful construct, very useful in distributed computing and beyond. It was introduced by Awerbuch et. al. [AGLP89] in the end of the eighties. These authors showed that strong (2O(√log n log log n), 2O(√log n log log n) network decompositions can be computed in 2O(√log n log log n) distributed time. Their result was improved at the beginning of nineties by Panconesi and Srinivasan [PS92], who showed that 2O(√log n in all the three expressions can be replaced by 2O(√log n. Around the same time Linial and Saks [LS93] devised an ingenious randomized algorithm that constructs weak (O(log n),O(log n)) network decompositions in O(log2 n) time. Awerbuch et. al. [ABCP96] devised a randomized algorithm that builds a strong (O(log n),O(log n)) network decomposition in O(log4 n) time, using very large messages and heavy local computations. It was however open till now if strong network decompositions with both parameters 2o(√log n) can be constructed in distributed 2o(√log n) time using short messages, or if a result of [LS93] can be strengthened to provide a strong (O(log n),O(log n)) network decomposition within O(log2 n) time (even using large messages). In this paper we answer these long-standing open questions in the affirmative, and show that strong (O(log n),O(log n)) network decompositions can be computed in O(log2 n) time. We also present a tradeoff between parameters of our network decomposition. Our work is inspired by and relies on the "shifted shortest path approach", due to Blelloch et. al. [BGKMPT11], and Miller et. al. [MPX13]. These authors developed this approach for PRAM algorithms for padded partitions. We adapt their approach to network decompositions in the distributed model of computation.