期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到3篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
一般图上的限制性k-node multicut问题 被引量：1
1
作者 杨惠娟 董延寿 严佩升 《宜宾学院学报》 2018年第6期53-56,共4页
对图论和组合优化经典multicut和multiwaycut问题中的一般图上的限制性k-node multicut问题进行讨论,该问题作为multicut问题的推广问题,它是NP难的,运用线性规划理论的知识设计了一个近似值为O((qlogq)(1/2))多项式时间算法.
关键词 限制性k-nodemulticut 近似算法 线性规划
在线阅读 下载PDF
树上限制性k-node multicut问题的近似算法
2
作者 杨惠娟 董延寿 林仕勋 《赤峰学院学报（自然科学版）》 2017年第18期7-8,共2页
树上的限制性k-node multicut问题(k-CMC(T))是NP难的,针对k-CMC(T)问题本文首先将问题分解成若干个最大流问题设计了近似值为k的算法其中k是参数.其次利用树的性质改进算法降低了算法的时间复杂度得到一个时间度为O(|V|~3log_2|V|)且... 树上的限制性k-node multicut问题(k-CMC(T))是NP难的,针对k-CMC(T)问题本文首先将问题分解成若干个最大流问题设计了近似值为k的算法其中k是参数.其次利用树的性质改进算法降低了算法的时间复杂度得到一个时间度为O(|V|~3log_2|V|)且近似值不变的算法.算法简单、易懂. 展开更多
关键词 限制性k-node multicut 近似算法 树 最大流
在线阅读 下载PDF
树上的限制性node multicut问题 被引量：2
3
作者 杨惠娟 《大理学院学报（综合版）》 CAS 2014年第12期21-25,共5页
割集问题在图论和组合优化中占有重要地位,限制性node multicut问题是割集问题的一类比较重要的推广问题。树上的限制性node multicut问题是值得研究的一个问题。首先说明此问题是NP难的,其次用线性规划理论中的互补松弛条件设计了一个... 割集问题在图论和组合优化中占有重要地位,限制性node multicut问题是割集问题的一类比较重要的推广问题。树上的限制性node multicut问题是值得研究的一个问题。首先说明此问题是NP难的,其次用线性规划理论中的互补松弛条件设计了一个近似值2且时间复杂度为O(max{kn,n log n})的算法。并进一步说明了通过算法得到的解具有半整数的性质。 展开更多
关键词 限制性node multicut 近似算法 互补松弛条件
在线阅读 下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部