Decomposing graphs into regions of small diameter
Decomposing graphs into regions of small diameter
复制标题
将图分解为小直径区域
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
M. Saks
中科院分区：
文献类型：
--
作者：
N. Linial;M. Saks
第36章将图分解成小直径的区域*Nathan Linialt Michael%.lss~图G=(V，E)的分解是将顶点集划分为子集(称为Lhk)。分解的直径最小。D使得属于块的同一连通分支的任何两个顶点的距离都是d。在这篇文章中，我们证明了(几乎是最好的)形式的陈述：.4n-顶点图有一个分解成几个块，每个块的直径都很小。这种分解提供了一种有效地分散分布式计算的工具。在[AGLP1]中，证明了每个图都有一个至多分解成直径至多为S(N)的块的S(N)，其中S(N)=~o(~loglog d h n)。利用Awerbuch[A]和Awerbuch和Peleg[AP]的技巧，我们证明了每个图都有直径()(Logn)到O(Logn)块的分解，从而改进了这一结果。此外，我们还给出了一个产生这种分解的随机分布式算法，该算法在时间0(Log2n)内运行。该结构可以被参数化，以提供在块数量和直径之间权衡的分解。我们表明，这种权衡对于两类图族来说几乎是最好的，第一类图族由单纯形的某些三角剖分的骨架组成，第二类图族由带有附加对角线的网格图组成。这两种情况的证明都依赖于组合拓扑学的基本结果，第一类是Sperner引理，第二类是Tucker引理。*这项工作部分得到了国家科学基金会合同DMS87-03541和CCR-8911388 t的支持，以色列耶路撒冷希伯来大学计算机科学系。+‘加州大学圣迭戈分校计算机科学与工程系，邮编：C-014.邮编：92093-0114.
Chapter 36 Decomposing Graphs into Regions of Small Diameter* Nathan Linialt Michael %.lss~ A decomposition of a graph G = (V, E) is a partition of the vertex set into subsets (called lhks). The diameter of a decomposition is the least. d such that any two vertices belonging to the same connected component of a block are at distance < d. In this paper we prove (nearly best possible) statements of the form: .4ny n–vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [AGLP1 it was shown that every graph has a decomposition into at most s(n) blocks of diameter at most s(n) for s(n) = ~o(~loglog d h n). usinga,technique of Awerbuch [A] and Awerbuch and Peleg [AP], we improve this result by showing that every graph has a decomposition of diameter ()(log n) into O(log n) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in time 0(log2 n). The construction can be parametrized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible for two families of graphs the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner’s lemma for the first class and Tucker’s lemma for the second. *This work was supported in part by NSF contracts DMS87-03541 and CCR-8911388 tDepartment of Computer Science, Hebrew University, Jerusalem, Israel. + ‘Department of Computer Science and Engineering, Mail Code C-014, University of California, San Diego, La Jolla, CA 92093-0114.