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

摘要：

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

关键词：可重构阵列、瑕点覆盖、点覆盖、图匹配、参数计算

所属期刊栏目：31

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金69928201;国家自然科学基金90104028;教育部长江学者奖励计划

在线出版日期：2004-06-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：184-188