双向图覆盖的启发式离散度求解

A Heuristic Solution of Bipartite Graph Cover Using Scatter Degree

为了解决大容量存贮器制造过程中因各种原因造成的成品率低的问题，或并行阵列中的容错重组问题，一般采用冗余修复的方法．该问题一般被归结为双向图的覆盖问题，且其复杂度被证明为ＮＰ．为加快求解速度，可以采用启发式算法求解．本文提出一种新的启发式算法求解，可以降低该问题的复杂度，提高修复效率．

In order to increase the throughout in process of memory manufacture, or solve the problem of fault tolerance in parallel array, common approach is spare allocation. The problem can be described as bipartite cover whose complex is NP hard. Heuristic algorithms are usually adopted to speed up feasible cover search. In this paper, a new heuristic algorithm is proposed where scatter degree is employed and complex of the algorithm is reduced to O(n). Based on it, another principle named relationless-seperatation of bipartite graph is proposed in this paper. Under this principle, we can disolve any bipartite graph into some relationless bipartite graph, so the complecx is reduced consequently.