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

Connected Dominating Sets Problem with Measured Functions

作　　者：马俊[1] 朱洪[1] 

机构地区：[1]复旦大学计算机科学与工程系智能信息处理开放实验室,上海200433

出　　处：《计算机科学》2006年第1期220-222,共3页Computer Science

基　　金：本文工作得到科技部基金(No.2001CCA03000);国家自然科学基金(No.60273045);上海科学技术发展基金(No.025115032)的支持。

摘　　要：连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题(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）.

关 键 词：支配集问题 组合优化 NP NP完全 多项式时间归约 NP难 测度函数 支配集 连通 NP完全性 多项式时间 

分 类 号：O211.6[理学—概率论与数理统计] O157.5[理学—数学]