multicut问题参数算法的改进
, PP. 1515-1523
Keywords: muliticut,node,multicut,集合划分,极大恰当划分
Abstract:
multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是np难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为o*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为o*的最好算法.
Full-Text
