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

作者：王建新; 许小双; 冯启龙; 李敏

来源：计算机研究与发展, 2008, 45(9): 1509-1516.

• 二分图
• 点覆盖
• 精确算法
• 参数计算
• 动态规划

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

• 单位
  中南大学; 浙江中烟工业有限责任公司