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