论文部分内容阅读
随着超大规模集成电路芯片生产技术的发展，单片芯片的集成度越来越高。要想一次生产出没有任何缺陷的芯片已不太可能。为了提高芯片的成品率，目前一种较为常用的方法是在超大规模集成电路芯片内部集成备用行（SR）和备用列（SC）用以替换阵列中有缺陷的行和列[5][6]，采用激光修复工艺可以很容易地实现这一修复过程[6]。Kuo和Fuchs[5]对该问题进行了开拓性的研究并给出了一些极有价值的结论：芯片可以抽象为一个M×N的阵列，对该阵列进行修复可以归结为用SR个行和SC个列对m×n的二分图进行覆盖。另外，Kuo和Fuchs还对如何修复给出了两个算法：一个是近似算法，到目前为止，该算法仍然是最高效的顶点覆盖问题的求解算法之一。但该算法的缺点在于不能保证求出顶点覆盖的最优解。也就是说，当一片芯片在事实上是可修复时却有可能在近似算法中得到不可修复的结论。另一个算法是启发式的分支界定算法，但该算法仅仅在中等规模的二分图中可行。Che在此前也曾提出过一种基于启发式的错误谱算法[1]，有效提高了求解的效率。但该算法仍然存在不能保证最优解的问题。 由于顶点覆盖问题的精确求解在实际应用中的需要，九十年代末期提出了参数计算理论，并很好的应用于顶点覆盖问题的求解上。Buss提出了第一个固定参数算法，并证明了该算法的运行时间复杂度为O(kn+2kk2k+2)[8]，该算法的时间复杂度随后被Downey和Pellows改进为O（An+2kk2）[9]。Balasubramanian教授率先在顶点覆盖问题的精确求解上突破了以2为底的指数复杂度。他提出的新算法证明了顶点覆盖问题可在O（kn+1.322718kk2）的时间复杂度内被求解[2]。最近，Chen和Kanj又提出了时间复杂度为O（kn+1.271kk2）的固定参数算法[3]。这是迄今为止已发表的最快的顶点覆盖问题算法。 但是，以上的算法并不能直接应用于受二分图约束的顶点覆盖问题（COnstraint Bipartite Vertex Cover,CBVC）求解。这是由于电路芯片的缺陷修复的实际问题造成的。但是，二分图本身也有许多有用的特性可以让我们减小问题的求解范围。 本论文应用固定参数算法，结合二分图的特殊性，，提出来一种简单但却十分有效的顶点覆盖算法，可在时间复杂度为O(1.26k1+k2+（k1+k2）n)求得CBVC的精确解。