Connected Dominating Sets Problem with Measured Functions
带测度函数的连通支配集问题

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