一种基于链暗示技术的Min-CVCB问题的精确算法

• 作者: 冯启龙 李敏 王建新 许小双
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 二分图 点覆盖 精确算法 参数计算 动态规划
• 年，卷（期）: 2008,（9）
• 所属期刊栏目: 算法理论
• 页码范围: 1509-1516
• 页数: 8页
• 分类号: TP391.41
• 字数: 7295字
• 语种: 中文

摘要

随着VLSI(超大规模集成电路)技术的发展,关于可重构阵列二分图的受约束最小点覆盖(Min-CVCB)问题受到了很多文献的关注.作为点覆盖问题的子问题,该问题已被证明是NP-完全问题.人们利用核心化和分支即使给出了时间复杂度为O((ku+k1)|G|+1.26ku+k1)的目前最好算法,然而仍不能满足实际工程的需要.通过进一步深入分析二分图的结构,对含有权值大于或等于3的块的连通子图分析其可能连接情况后充分利用"链暗示"技术和分枝搜索技术来建立起新的搜索递推关系;对于分枝后的块提出了一种动态规划算法,其可在多项式时间内完成处理.整个参数算法的运行时间为O((ku+k1)|G|+1.1892ku+k1),极大地改进了目前的最好结果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	中南大学信息科学与工程学院	371	3185	23.0	39.0
2	李敏	中南大学信息科学与工程学院	116	690	14.0	20.0
3	许小双	中南大学信息科学与工程学院	7	31	4.0	5.0
7	冯启龙	中南大学信息科学与工程学院	11	38	4.0	6.0