2-Club簇图顶点删除问题改进参数算法

来源期刊:中南大学学报(自然科学版)2018年第2期

论文作者:冯启龙 谭冠兰 孙龙志 郑莹 谭培强

文章页码:371 - 378

关键词:2-club;2-club簇图顶点删除;固定参数算法

Key words:2-club; 2-club cluster vertex deletion; fixed-parameterized algorithm

摘    要:2-club簇图修改问题是经典的NP难问题。对通过对2-club簇图修改问题的参数算法进行研究,提出简化问题实例的若干规则。基于对2-club簇图结构的分析和提出的简化规则,并采用自顶向下的分支方法,提出时间复杂度为O*(3.24k)的固定参数算法,降低了目前求解该问题的时间复杂度。

Abstract: 2-club cluster graph modification problems are classical NP-hard problems. The parameterized algorithms were studied for the 2-club cluster graph modification problems, and several reduction rules were presented to reduce the size of input instance. Based on the structure analysis of the 2-club cluster graph and the reduction rules presented, by applying a top-down approach, a fixed-parameterized algorithm with running time O*(3.24k) was presented, which improves the current algorithm solving the 2-club cluster graph modification problems.

有色金属在线官网  |   会议  |   在线投稿  |   购买纸书  |   科技图书馆

中南大学出版社 技术支持 版权声明   电话:0731-88830515 88830516   传真:0731-88710482   Email:administrator@cnnmol.com

互联网出版许可证:(署)网出证(京)字第342号   京ICP备17050991号-6      京公网安备11010802042557号