Improved sparse covers for graphs excluding a fixed minor
Improved sparse covers for graphs excluding a fixed minor
复制标题
改进了图形的稀疏覆盖，不包括固定次要的
DOI：
10.1145/1281100.1281112
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Srikanta Tirthapura
中科院分区：
文献类型：
--
作者：
C. Busch;Ryan LaFortune;Srikanta Tirthapura
我们考虑平面图以及排除固定子图的其他图的稀疏覆盖的构建。我们提出一种算法，该算法为每个节点的γ - 邻域给出一个覆盖。对于平面图，覆盖的半径不超过24γ - 8，度（最大聚类重叠）不超过18。对于每一个排除固定子图的n个节点的图，我们提出一种算法，该算法产生的覆盖半径不超过4γ，度为O(log n)。
这相对于平面图以及排除固定子图的图的先前结果是一个重大改进；为了获得半径为O(γ)的聚类，之前要求度是n的多项式。由于稀疏覆盖在分布式计算中有许多应用，包括紧凑路由、分布式目录和同步器，对于排除固定子图的图类，我们改进的覆盖构建导致所有这些问题的算法得到改进。
We consider the construction of sparse covers for planar graphs and other graphs that exclude a fixed minor. We present an algorithm that gives a cover for the γ-neighborhood of each node. For planar graphs, the cover has radius no more than 24γ-8 and degree (maximum cluster overlaps) no more than 18. For every n node graph that excludes a fixed minor, we present an algorithm that yields a cover with radius no more than 4γ and degree O(log n).
This is a significant improvement over previous results for planar graphs and for graphs excluding a fixed minor; in order to obtain clusters with radius of O(γ), it was required to have degree polynomial in n. Since sparse covers have many applications in distributed computing, including compact routing, distributed directories and synchronizers, our improved cover construction results in improved algorithms for all these problems, for the class of graphs that exclude a fixed minor.