| 二分图约束的顶点覆盖问题的快速算法 |
| |
| 引用本文： | 何峰,车文刚.二分图约束的顶点覆盖问题的快速算法[J].昆明理工大学学报(理工版),2003,28(5):85-89. |
| |
| 作者姓名： | 何峰 车文刚 |
| |
| 作者单位： | 昆明理工大学,信息工程与自动化学院,云南,昆明,650051 |
| |
| 摘 要： | 对超大规模集成电路芯片(VLSI)的缺陷修复可归结为受二分图约束的顶点覆盖问题，该问题属于NP完全问题。目前仍不能在多项式时间内对该问题求解。本文应用参数计算理论，将问题化简为与输入问题规模无关的问题来求解。并利用二分图的特性，提出了一种简单、高效的算法，大大提高了修复速度。
|
| 关 键 词： | 超大规模集成电路芯片 二分图 顶点覆盖问题 NP完全问题 参数算法 缺陷修复 搜索树 |
| 文章编号： | 1007-855X(2003)05-0085-05 |
| 修稿时间： | 2003年4月30日 |
An Efficient Algorithm for Constraint Bipartite Vertex Cover |
| |
| HE Feng,CHE Wen gang.An Efficient Algorithm for Constraint Bipartite Vertex Cover[J].Journal of Kunming University of Science and Technology(Natural Science Edition),2003,28(5):85-89. |
| |
| Authors: | HE Feng CHE Wen gang |
| |
| Abstract: | The fault coverage problem for reconfigurable arrays has received as constraint bipartite vertex cover problem, which is proved as a NP-complete. It can't be resolved in polynomial running time. The theory of parameterised computation is used to reduce the kernel of problem which is independent of the original problem. Furthermore, the algorithm's running time is bounded by the study for the characteristics of the bipartite graph. |
| |
| Keywords: | reconfigurable arrays bipartite graph vertex cover graph matching parameterised computation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
