On Approximating (Connected) 2-Edge Dominating Set by a Tree
On Approximating (Connected) 2-Edge Dominating Set by a Tree
复制标题
DOI：
10.1007/s00224-017-9764-y
复制
发表时间：
2016-06
影响因子：
0.5
通讯作者：
Toshihiro Fujito;Tomoaki Shimoda
中科院分区：
文献类型：
--
作者：
Toshihiro Fujito;Tomoaki Shimoda
边支配集问题(EDS)是指计算一个最小尺寸的边集，使得每条边都被其中的某条边支配。本文考虑了EDS的一个变种，它结合了多重支配和连通支配的扩展。在b-EDS问题中，每条边都需要两次支配，连通的边支配集需要连通，而它必须在树覆盖中形成一棵树。虽然EDS、b-EDS和连通EDS(或树覆盖)中的每一个都已经被很好地研究过，每个已知在2(或通常是8/3的Forb-EDS)内可逼近，但当这些扩展同时施加到EDS上时，与(顶点)支配集问题的情况不同，什么都不知道。我们考虑连通的2-EDSand2-树覆盖(即，2-EDS和树覆盖的组合)，并给出了一个在2内逼近它们的多项式算法。此外，我们将证明所计算的单树不大于2-EDS(不一定是连通的)最优树的两倍，从而也同样地逼近2-EDS。这也意味着具有聚类性的2-EDS也可以在2内近似。
Theedge dominating setproblem (EDS) is to compute a minimum size edge set such that every edge is dominated by some edge in it. This paper considers a variant of EDS with extensions of multiple and connected dominations combined. In theb-EDS problem, each edge needs to be dominatedbtimes.Connected EDSrequires an edge dominating set to be connected while it has to form a tree inTree Cover. Although each of EDS,b-EDS, andConnected EDS(orTree Cover) has been well studied, each known to be approximable within 2 (or 8/3 forb-EDS in general), nothing is known when these extensions are imposed simultaneously on EDS unlike in the case of the (vertex) dominating set problem. We considerConnected 2-EDSand2-Tree Cover(i.e., a combination of 2-EDS andTree Cover), and present a polynomial algorithm approximating each within 2. Moreover, it will be shown that the single tree computed is no larger than twice the optimum for (not necessarily connected) 2-EDS, thus also approximating 2-EDS equally well. It also implies that 2-EDS with clustering properties can be approximated within 2 as well.