10.3969/j.issn.1002-137X.2006.01.061
带测度函数的连通支配集问题
连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题(CDS(F)),使得它具有更广的应用范围.文中首先给出问题的形式定义,证明了它在各种情形下的NP完全性,并给出多项式时间的近似算法,它的近似度为Ln△+3(△为图中顶点的最大度数).
支配集问题、组合优化、NP、NP完全、多项式时间归约、NP难
33
TP3(计算技术、计算机技术)
科技部资助项目2001CCA03000;中国科学院资助项目60273045;上海市科技发展基金025115032
2006-03-30(万方平台首次上网日期,不代表论文的发表时间)
共3页
220-222