二分图约束的顶点覆盖问题的快速算法

摘要：

对超大规模集成电路芯片(VLSI)的缺陷修复可归结为受二分图约束的顶点覆盖问题,该问题属于NP完全问题.目前仍不能在多项式时间内对该问题求解.本文应用参数计算理论,将问题化简为与输入问题规模无关的问题来求解.并利用二分图的特性,提出了一种简单、高效的算法,大大提高了修复速度.

关键词：可修复阵列、二分图、顶点覆盖、匹配、参数计算

所属期刊栏目：28

分类号：TP393(计算技术、计算机技术)

在线出版日期：2004-04-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：85-89