论文部分内容阅读
本文引入测度函数的概念，提出了带测度函数的连通支配集问题(CDS(F))，使得它具有更广的应用范围。文章给出了问题的形式定义，证明了它在几种情形下的NP完全性，并给出了多项式时间的近似算法，它的近似度为ln｜V｜+3，给出了一个不可近似下界。文章同时指出，对子不可近似性的结果，似乎还可以提高，也许从集合覆盖来规约是一个方向。