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

为了大容量存贮器制造过程中因缺陷而造成成品率低的问题，或并行阵列中的容错重组问题，一般采用冗余修复的方法，该问题可以归结为对二分图的覆盖，且该问题属于ＮＰ完全问题。

Independent Separation of Bipartite Graph and its Application in Cover Problem

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.