Multicut问题参数算法的改进

摘要：

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

关键词：Muliticut、Node Multicut、集合划分、极大恰当划分

所属期刊栏目：21

分类号：TP301(计算技术、计算机技术)

资助基金：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

在线出版日期：2010-09-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1515-1523