Connected Dominating Sets
Connected Dominating Sets
复制标题
DOI：
10.2174/978160805018510901010019
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Xiuzhen Cheng;Feng Wang
中科院分区：
文献类型：
--
作者：
Xiuzhen Cheng;Feng Wang
问题定义考虑一个图G =（V，E）. V的子集C称为控制集，如果每个顶点都在C中或与C中的一个顶点相邻。此外，如果C诱导的子图是连通的，则C称为连通控制集。具有最小基数的连通支配集称为最小连通支配集（MCDS）。计算MCDS是一个NP难问题，并且对于ρ < 1，没有具有性能比ρH（n）的多项式时间近似，除非NP <$DTIME（n ln），其中H是调和函数，并且n是输入图的最大度[10]。单位圆盘是半径为1的圆盘。单位圆盘图（UDG）与欧几里得平面中的一组单位圆盘相关联。每个节点都位于单位圆盘的中心。两个节点u和v之间存在边，当且仅当|UV| ≤ 1，其中|UV|是u和v之间的欧几里得距离。这意味着两个节点u和v与边相连，当且仅当u的圆盘覆盖v，v的圆盘覆盖u。在单位圆盘图中计算MCDS仍然是NP难的。在单位圆盘图中构造MCDS的一个好的近似有多难？Cheng等人[5]通过提出多项式时间近似方案回答了这个问题。
PROBLEM DEFINITION Consider a graph G = (V,E). A subset C of V is called a dominating set if every vertex is either in C or adjacent to a vertex in C. If, furthermore, the subgraph induced by C is connected, then C is called a connected dominating set. A connected dominating set with a minimum cardinality is called a minimum connected dominating set (MCDS). Computing a MCDS is an NP-hard problem and there is no polynomial-time approximation with performance ratio ρH(∆) for ρ < 1 unless NP ⊆ DTIME(n ln ) where H is the harmonic function and ∆ is the maximum degree of the input graph [10]. A unit disk is a disk with radius one. A unit disk graph (UDG) is associated with a set of unit disks in the Euclidean plane. Each node is at the center of a unit disk. An edge exists between two nodes u and v if and only if |uv| ≤ 1 where |uv| is the Euclidean distance between u and v. This means that two nodes u and v are connected with an edge if and only if u’s disk covers v and v’s disk covers u. Computing an MCDS in a unit disk graph is still NP-hard. How hard is it to construct a good approximation for MCDS in unit disk graphs? Cheng et al. [5] answered this question by presenting a polynomial-time approximation scheme.