ISSN 1000-1239 CN 11-1777/TP

• 论文 •

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

1. 1（中南大学信息科学与工程学院 长沙 410083） 2（浙江中烟工业有限责任公司信息中心 杭州 310009） （jxwang@mail.csu.edu.cn）
• 出版日期: 2008-09-15

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

Wang Jianxin1, Xu Xiaoshuang1,2, Feng Qilong1, and Li Min1

1. 1（School of Information Science and Engineering, Central South University, Changsha 410083） 2（Information Center, China Tobacco Zhejiang Industrial Co. Ltd., Hangzhou 310009）
• Online: 2008-09-15

Abstract: 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（（k\-u+k\-l）|G|+1.26\+\{k\-u+k\-l\}）, 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（（k\-u+k\-l）|G|+1.1892\+\{k\-u+k\-l\}）, which greatly improves the current best result.