节点文献

Multicut问题参数算法的改进

Improved Parameterized Algorithm for the Multicut Problem

  • 推荐 CAJ下载
  • PDF下载
  • 不支持迅雷等下载工具,请取消加速工具后下载。

【作者】 刘运龙王建新陈建二

【Author】 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)

【机构】 中南大学信息科学与工程学院湖南师范大学继续教育学院

【摘要】 Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*(︱(2l)~(1/2)︱2l4k)的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*(2klkk4k3)的最好算法.

【Abstract】 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)︱2l4k) for the problem,in which l denotes the number of terminal pairs and k denotes the number of removed vertices.This algorithm significantly improves the previous one of running time O*(2 kl kk 4k3).

【基金】 国家自然科学基金Nos.60433020,60773111;国家重点基础研究发展计划(973)No.2008CB317107;新世纪优秀人才支持计划No.NCET-05-0683~~
  • 【文献出处】 软件学报 ,Journal of Software , 编辑部邮箱 ,2010年07期
  • 【分类号】TP301.6
  • 【被引频次】3
  • 【下载频次】141
节点文献中: 

本文链接的文献网络图示:

本文的引文网络