计算机科学 ›› 2006, Vol. 33 ›› Issue (1): 220-222.
• • 上一篇 下一篇
马俊 朱洪
出版日期:
发布日期:
基金资助:
MA Jun, ZHU Hong （Laboratory for Intelligent Information Processing, Fudan University, Shanghai 200433）
Online:
Published:
摘要： 连通支配集问题在网络广播上有着广泛的应用，本文引入测度函数的概念，提出了带测度函数的连通支配集问题（CDS（F）），使得它具有更广的应用范围。文中首先给出问题的形式定义，证明了它在各种情形下的NP完全性，并给出多项式时间的近似算法，它的近似度为Ln△＋3（△为图中顶点的最大度数）。
关键词: 支配集问题 组合优化 NP,NP完全 多项式时间归约 NP难 测度函数 支配集 连通 NP完全性 多项式时间
Abstract: 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 g
Key words: Dominating set, Combinatorial optimization, NP, NP-complete, Polynomial reduction, NP-hard
马俊 朱洪. 带测度函数的连通支配集问题[J]. 计算机科学, 2006, 33(1): 220-222. https://doi.org/
MA Jun, ZHU Hong （Laboratory for Intelligent Information Processing, Fudan University, Shanghai 200433）. [J]. Computer Science, 2006, 33(1): 220-222. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2006/V33/I1/220
Cited
首页