简介概要

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

来源期刊：昆明理工大学学报(自然科学版)2003年第5期

论文作者：何峰车文刚

文章页码：85 - 89

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

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

详情信息展示

何峰，车文刚

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