%0 Journal Article
%T Connected Dominating Sets Problem with Measured Functions
带测度函数的连通支配集问题
%A MA Jun
%A ZHU Hong
%A
马俊
%A 朱洪
%J 计算机科学
%D 2006
%I
%X 连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题(CDS(F)),使得它具有更广的应用范围。文中首先给出问题的形式定义,证明了它在各种情形下的NP完全性,并给出多项式时间的近似算法,它的近似度为Ln△+3(△为图中顶点的最大度数)。
%K NP
支配集问题
%K 组合优化
%K NP完全
%K 多项式时间归约
%K NP难
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=9672CB434232A69A&yid=37904DC365DD7266&vid=27746BCEEE58E9DC&iid=CA4FD0336C81A37A&sid=1D67BE204FBF4800&eid=8B59EA573021D671&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=7