%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