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

An Exact Algorithm Based on Chain Indication for Min-CVCB Problem

作　　者：王建新[1] 许小双[1] 冯启龙[1] 李敏[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机研究与发展》2008年第9期1509-1516,共8页Journal of Computer Research and Development

基　　金：国家“九七三”重点基础研究发展规划基金项目(2008CB317107);国家自然科学基金项目(60433020,60773111);国家教育部新世纪优秀人才支持计划(NCET-05-0683);国家教育部创新团队资助项目(IRT0661)~~

摘　　要：随着VLSI(超大规模集成电路)技术的发展,关于可重构阵列二分图的受约束最小点覆盖(Min-CVCB)问题受到了很多文献的关注.作为点覆盖问题的子问题,该问题已被证明是NP-完全问题.人们利用核心化和分支即使给出了时间复杂度为O((ku+kl)|G|+1.26ku+kl)的目前最好算法,然而仍不能满足实际工程的需要.通过进一步深入分析二分图的结构,对含有权值大于或等于3的块的连通子图分析其可能连接情况后充分利用"链暗示"技术和分枝搜索技术来建立起新的搜索递推关系;对于分枝后的块提出了一种动态规划算法,其可在多项式时间内完成处理.整个参数算法的运行时间为O((ku+kl)|G|+1.1892ku+kl),极大地改进了目前的最好结果.With the technical development of VLSI （very large scale integrated circuit）, the constrained minimum vertex cover in bipartite graphs （Min-CVCB） for re-configurable arrays has attracted considerable attention in the literature. The Min-CVCB problem is a classical sub-problem of vertex cover problem, and has been proved to be NP-complete. At present, the best exact algorithm for the problem is proposed by using kernelization and branching technology with running time bounded by O（（ku4-k1）｜G＋ 1.26ku＋k1）, which is still unable to satisfy the requirement of the industry development. Based on the above result, an improved parameterized algorithm is presented for the Min-CVCB problem. For the Min-CVCB problem, a more detailed analysis is given for the structure of the bipartite graph and list all the possible joint of the blocks whose weight are at least 3 in a case-by-case exhaustive manner. Based on the above analysis, full use is made of the chain implication and bounded searching technology is used to construct new recurrence relations. For the remaining blocks generated by branching, dynamic programming technology is used to handle, which can be solved in polynomial time. The total time complexity of this algorithm is bounded by O（（ku ＋ k1） ｜G｜＋1. 1892ku＋k1 ）, which greatly improves the current best result.

关 键 词：二分图 点覆盖 精确算法 参数计算 动态规划 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]