二分图的无关分解及其在覆盖问题中的应用_中文_期刊

二分图的无关分解及其在覆盖问题中的应用

更新时间：2019-05-21 访问次数：

关键词：二分图　　覆盖问题　　无关分解　　无关联子图

发明人：车文刚，苏磊，王宏祥，焦越

作者单位：云南工业大学信息与电子工程学院　　（650051）

内容提要：为了解决大容量存贮器制造过程中因缺陷而造成成品率低的问题，或并行阵列中的容错重组问题，一般采用冗余修复的方法，该问题可以归结为对二分图的覆盖，且该问题属于NP完全问题．本文提出一个新的二分图无关分解方法．运用这一方法，可将一个二分图分解为多个互不关联的子图，然后分别在各子图中对缺陷进行覆盖，从而使该问题复杂度降低，提高修复速度．

期刊名：电子学报

期号：第5期

年份：1998

页数：42-47

二分图的无关分解及其在覆盖问题中的应用

推荐内容

热门内容