2. 您的位置
3. 首页
4. 期刊论文
5. 限制的星划分问题

限制的星划分问题

来源 :云南大学学报：自然科学版 | 被引量 : 0次 | 上传用户：wanghua035871

【摘 要】

：

研究了边赋权图上2类具有权重限制L的最小基数星划分问题-最小基数S（L）划分问题和最小基数S∑（L）划分问题的困难性.得到如下结果：①证明了一般图上最小基数S（L）划分问题的NP-完全性;

【作 者】

：

张同全 李伟东 李建平 

【机 构】

：

云南大学物理科学技术学院非线性中心,云南大学数学与统计学院数学系

【出 处】

：

云南大学学报：自然科学版

【发表日期】

：

2008年2期

【关键词】

：

最小基数 S(L)划分问题 S∑(L)划分问题 NP-完全性 近似算法 minamal cardinality S（L） partition problem S 

【基金项目】

：

国家自然科学研究基金资助项目（10561009）,云南省教育厅科学研究基金项目（06J011A）.

下载到本地 , 更方便阅读

下载此文 赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

研究了边赋权图上2类具有权重限制L的最小基数星划分问题-最小基数S（L）划分问题和最小基数S∑（L）划分问题的困难性.得到如下结果：①证明了一般图上最小基数S（L）划分问题的NP-完全性;②证明了一般图上最小基数S∑（L）划分问题的NP-完全性,并证明了对于任意小的正数ε,一般图上的最小基数S∑（L）划分问题不存在（3/2-ε）-近似算法,除非P=NP.

其他文献