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

Independent Separation of Bipartite Graph and its Application in Cover Problem

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

In order to solve the problem of low yield by defects in VLSI manufacture,or that of fault tolerance in parallel arrays, we usually employ a redundant repair method supported by laser repair technology. The problem of how to use limited spares to repair a whole faulty array can be described as a cover problem of bipartite graph and was proved NP-hard. In this paper, a new approach is proposed where the concept of independent subgraph is employed in separation of a bipartite graph. Based on this method, a bipartite graph is decomposed into some independent and smaller bipartite subgraphs. Thus the cover problem of bipartite graph becomes that of independent subgraph,so the complexity of the problem is reduced and the analysis time is decreased consequently.