| 摘要: |
| Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*的最好算法. |
| 关键词: Muliticut Node Multicut 集合划分 极大恰当划分 |
| DOI： |
| 分类号: |
| 基金项目: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 (新世纪优秀人才支持计划) |
|
| Improved Parameterized Algorithm for the Multicut Problem |
|
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*. |
| Key words: Muliticut Node Multicut set partition maximal proper partition |
