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

• 作者: 何峰 车文刚
• 来源期刊: 昆明理工大学学报（理工版）
• 学科: 工学
• 关键词: 可修复阵列 二分图 顶点覆盖 匹配 参数计算
• 年，卷（期）: 2003,（5）
• 所属期刊栏目: 信息工程与自动化
• 页码范围: 85-89
• 页数: 5页
• 分类号: TP393
• 字数: 5522字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-855X.2003.05.021

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	车文刚	昆明理工大学信息工程与自动化学院	52	521	9.0	22.0
2	何峰	昆明理工大学信息工程与自动化学院	2	2	1.0	1.0