Improved Algorithms about Minimum Fault Coverage in Reconfigurable Arrays
一种可重构阵列的最小瑕点覆盖算法

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.