东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

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

ISSN号：1000-1239
期刊名称：《计算机研究与发展》
时间：0
分类：TP391.41[自动化与计算机技术—计算机应用技术;自动化与计算机技术—计算机科学与技术]
作者机构：[1]中南大学信息科学与工程学院,长沙410083, [2]浙江中烟工业有限责任公司信息中心,杭州310009
相关基金：国家“九七三”重点基础研究发展规划基金项目（2008CB317107）;国家自然科学基金项目（60433020,60773111）;国家教育部新世纪优秀人才支持计划（NCET-05-0683）;国家教育部创新团队资助项目（IRT0661） The theory of parameterized computation and complexity is a recently developed sub-area in theoretical computer science. The theory aims at practically solving a large number of computational problems that are theoretically intractable. Vertex cover is an important NP-hard problem. Constrained minimum cover in bipartite graphs （Min-CVCB） problem is a classical sub- problem in vertex cover, which has important application in the development of VLSI technology. It has been extensively studied in the last two decades. However, the best exact algorithm for this problem at present is still unable to satisfy the requirement of the industry development. In this paper, we further analyze the structure of the problem and list all the possible joint of the blocks whose weight is at least 3 in a case-by-case exhaustive manner, and then use chain implication and bounded search-trees technology to construct new recurrence relations. Then, we use dynamic programming to handle the remaining blocks generated by branching. Finally, we present the algorithm to solve the Min-CVCB problem with time O（（ku ＋k1 ）｜G｜＋ 1.1892ku＋k1）. Our algorithm reduces the base by near 0.08 （from 1.26 to 1. 1892） from the previous known algorithm for the Min-CVCB problem. Our work is supported by the National Basic Research 973 Program of China （2008CB317107）, the National Natural Science Foundation of China under grant Nos 60433020 and 60773111, the Program for New Century Excellent Talents in University of China under grant No. NCET-05-0683, and the Program for Changjiang Scholars and Innovative Research Team in University of China under grant No. IRT0661.

关键词：二分图, 点覆盖, 精确算法, 参数计算, 动态规划, bipartite graph, vertex cover, exact algorithm, parameterized computation, dynamic programming

中文摘要：

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

英文摘要：

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.

同期刊论文项目