| 
  中国学术期刊网络出版总库
  关闭
Multicut问题参数算法的改进  
   推荐 CAJ下载 PDF下载
【英文篇名】 Improved Parameterized Algorithm for the Multicut Problem
【下载频次】 ★★★☆
【作者】 刘运龙; 王建新; 陈建二;
【英文作者】 LIU Yun-Long1; 2; WANG Jian-Xin1; CHEN Jian-Er1 1(School of Information Science and Engineering; Central South University; Changsha 410083; China) 2(School of Continuing Education; Hu'nan Normal University; Changsha 410013; China);
【作者单位】 中南大学信息科学与工程学院; 湖南师范大学继续教育学院;
【文献出处】 软件学报 , Journal of Software, 编辑部邮箱 2010年 07期  
期刊荣誉：中文核心期刊要目总览  ASPT来源刊  中国期刊方阵  CJFD收录刊
【中文关键词】 Muliticut; Node Multicut; 集合划分; 极大恰当划分;
【英文关键词】 Muliticut; Node Multicut; set partition; maximal proper partition;
【摘要】 Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*(︱(2l)～(1/2)︱~(2l)4~k)的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*(2klkk4k3)的最好算法.
【英文摘要】 The Multicut problem is for a given graph and a given collection of terminal pairs to find a vertex set of minimum size such that the two terminals in any pair are not connected after deletion of this vertex set.This problem is NP-hard.Based on the deep analysis of its structural characteristics,employing the strategy of set partition and the improved results of another related problem,this paper proposes a parameterized algorithm of running time O*(︱(2l)～(1/2)︱~(2l)4~k) for the problem,in which l denotes t...
【基金】 国家自然科学基金Nos.60433020,60773111; 国家重点基础研究发展计划(973)No.2008CB317107; 新世纪优秀人才支持计划No.NCET-05-0683~~
【更新日期】 2010-09-07
【分类号】 TP301.6
【正文快照】 Multicut问题即给定一个无向图G和其中l个顶点对(si,ti)(1≤i≤l,l≥3),目标是从图G中删除最少的顶点(或者边),使得任意给定顶点对的两个顶点si和ti之间均没有路径[1].该问题是图论中一个最基本的优化问题,是研究计算机通信网络可靠性和鲁棒性的一种重要模型,在聚类、超大规模?

xxx
【读者推荐文章】中国期刊全文数据库
【相似文献】
中国期刊全文数据库
中国优秀硕士学位论文全文数据库
中国博士学位论文全文数据库
中国重要会议论文全文数据库
中国重要报纸全文数据库
中国学术期刊网络出版总库
点击下列相关研究机构和相关文献作者，可以直接查到这些机构和作者被《中国知识资源总库》收录的其它文献，使您全面了解该机构和该作者的研究动态和历史。
【文献分类导航】从导航的最底层可以看到与本文研究领域相同的文献，从上层导航可以浏览更多相关领域的文献。

工业技术
　 自动化技术、计算机技术
　　 计算技术、计算机技术
　　　 一般性问题
　　　　 理论、方法
　　　　　 算法理论
  
 
  CNKI系列数据库编辑出版及版权所有：中国学术期刊(光盘版)电子杂志社
中国知网技术服务及网站系统软件版权所有：清华同方知网(北京)技术有限公司
其它数据库版权所有：各数据库编辑出版单位（见各库版权信息）
京ICP证040431号    互联网出版许可证 新出网证（京）字008号