| Multicut问题参数算法的改进 |
| |
| 引用本文： | 刘运龙,王建新,陈建二. Multicut问题参数算法的改进[J]. 软件学报, 2010, 21(7): 1515-1523. DOI: 10.3724/SP.J.1001.2010.03625 |
| |
| 作者姓名： | 刘运龙 王建新 陈建二 |
| |
| 作者单位： | 中南大学,信息科学与工程学院,湖南,长沙,410083;湖南师范大学,继续教育学院,湖南,长沙,410013;中南大学,信息科学与工程学院,湖南,长沙,410083 |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant Nos.60433020, 60773111 (国家自然科学基金); the National Basic Research Program of China under Grant No.2008CB317107 (国家重点基础研究发展计划(973)); the Program for New Century Excellent Talents in University of China under Grant No.NCET-05-0683 (新世纪优秀人才支持计划) |
| |
| 摘 要： | Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*的最好算法.
|
| 关 键 词： | Muliticut Node Multicut 集合划分 极大恰当划分 |
| 收稿时间： | 2008-09-12 |
| 修稿时间： | 2009-03-31 |
Improved Parameterized Algorithm for the Multicut Problem |
| |
| LIU Yun-Long,WANG Jian-Xin and CHEN Jian-Er. Improved Parameterized Algorithm for the Multicut Problem[J]. Journal of Software, 2010, 21(7): 1515-1523. DOI: 10.3724/SP.J.1001.2010.03625 |
| |
| Authors: | LIU Yun-Long WANG Jian-Xin CHEN Jian-Er |
| |
| 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* 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*. |
| |
| Keywords: | Muliticut Node Multicut set partition maximal proper partition |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
