带测度函数的连通支配集问题

Connected Dominating Sets Problem with Measured Functions

连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题(CDS(F)),使得它具有更广的应用范围。文中首先给出问题的形式定义,证明了它在各种情形下的 NP 完全性,并给出多项式时间的近似算法,它的近似度为 Ln△+3(△为图中顶点的最大度数)。

Connected dominating sets problem has widely used in network broadcast. This paper introduces the concept of measured function and defines connected dominating sets problem with measured functions （CDS （F））. A formal definition of the CDS （F） is firstly given, whose NP property is then proved in variant situations. We also present an approximation algorithm with approximation ratio Ln△＋3（△ is maximal degree of the vertex in our concerned graph）.