%0 Journal Article
%T Improved Algorithms about Minimum Fault Coverage in Reconfigurable Arrays<br>一种可重构阵列的最小瑕点覆盖算法
%A ZHANG Zu-Ping CHEN Jian-Er
%A <br>张祖平
%A 陈建二
%J 计算机科学
%D 2004
%I 
%X 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.
%K Reconfigurable arrays
%K Fault coverage
%K Vertex cover
%K Graph matching
%K Parameterized computation<br>超大规模集成电路
%K 电路芯片
%K 最小瑕点覆盖算法
%K 可重构阵列
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=83A2B9270508C9E4&yid=D0E58B75BFD8E51C&vid=4AD960B5AD2D111A&iid=E158A972A605785F&sid=798FBE8DE1A255B1&eid=847B14427F4BF76A&journal_id=1002-137X&journal_name=计算机科学&referenced_num=1&reference_num=6