Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers
Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers
复制标题
DOI：
10.1007/978-3-319-30139-6_20
复制
发表时间：
2016-03
期刊：
影响因子：
--
通讯作者：
Toshihiro Fujito;D. Suzuki
中科院分区：
文献类型：
--
作者：
Toshihiro Fujito;D. Suzuki
局部算法是确定性的（即，非随机）分布式算法在一个匿名的端口编号的网络中运行在一个常数数量的同步轮，这项工作研究了这种算法的近似性能。所处理的问题是b-边支配集（b-EDS），它是边支配集（EDS）问题的多重支配形式; t-全顶点覆盖（t-TVC），它是顶点覆盖问题的一个变种，具有聚类性质。在观察到EDS和2-TVC分别在4和3内是可近似的之后，使用用于在双色图中找到最大匹配的局部算法的单次运行，将看到，针对双色图运行最大匹配局部算法两次，2-EDS和3-TVC可以分别在因子2和3内近似。
A local algorithm is a deterministic (i.e., non-randomized) distributed algorithm in an anonymous port-numbered network running in a constant number of synchronous rounds, and this work studies the approximation performance of such algorithms. The problems treated areb-edge dominating set (b-EDS) that is a multiple domination version of the edge dominating set (EDS) problem, andt-total vertex cover (t-TVC) that is a variant of the vertex cover problem with a clustering property. After observing that EDS and 2-TVC are approximable within 4 and 3, respectively, using a single run of the local algorithm for finding a maximal matching in a bicolored graph, it will be seen that running the maximal matching local algorithm for bicolored graph twice, 2-EDS and 3-TVC can be approximated within factors 2 and 3, respectively.