一种可重构阵列的最小瑕点覆盖算法

Improved Algorithms about Minimum Fault Coverage in Reconfigurable Arrays

关于可重构阵列的瑕点覆盖问题受到了很多文献的关注,特别地,关于可重构阵列的最小瑕点覆盖问题等价于二分图的受约束最小点覆盖问题,并被证明是NP-完全问题.针对本问题提出的算法运行时间为O(1.19k+kn),这里k为可替换行与列的数目,改进了原有的最好结果,其运行时间为O(1.26k+kn),较好地组合并扩展了研究参数计算的最新技术与经典匹配理论,且具有较好的实用价值.这是关于可重构阵列的最小瑕,点覆盖问题算法又一较大的改进,也是目前最小点覆盖问题相关参数算法的较有意义的改进.

The fault coverage problem for reconfigurable arrays has received considerable attention in the literature. In particular , the minimum fault coverage problem for reconfigurable arrays is equivalent to a constrained minimum vertex cover problem on bipartite graphs and the problem has been proved to be NP-complete. This paper gives an algorithm developed for the problem,in which classical results in matching theory and recently developed techniques in the study of parameterized computation are nicely combined and extended. The algorithm is practically efficient with its running time bounded by O(1. I9k + kn) .where k is the minimum number of replacement rows and columns. The algorithm is a significant improvement over the previous algorithms for the minimum fault coverage problem for reconfigurable arrays with its running time bounded by O (1. 26k + kn), as well as over the related parameterized algorithms for the minimum vertex cover problem.