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

摘要

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