二分图的受约束最小点覆盖问题研究

摘要

随着VLSI(超大规模集成电路)技术的发展，关于可重构阵列的二分图受约束最小点覆盖问题(简称Min-CVCB问题)受到了很多文献的关注，大量这方面的论文发表在IEEE的重要期刊和年会上。该问题已被证明是NP-完全问题。 目前求解 Min-CVCB 问题的精确算法的运行时间为O((k<,u>+k<,l>|G|+1.26<'ku+kl>)，其中k<,u>、k<,l>分别表示备用行和备用列的数目。本文进一步深入分析二分图的结构，对含有权值大于或等于3的块的连通子图首先分析其可能连接情况，然后充分利用“链暗示”技术和分枝搜索技术建立新的搜索递推关系；对于分枝后的块，本文提出了一种动态规划算法，使其可在多项式时间内完成处理。整个算法的运行时间为O((k<,u>+k<,l>|G|+1.1892<'ku+kl>)。在此基础上，本文通过进一步运用参数计算技术和图论知识，研究了Min-CVCB问题的一个亚指数时间算法，该算法尚需进一步完善和补充。 同时，针对传统启发式算法和当前精确算法的不足，本文通过进一步深入运用参数计算技术和图论技术，提出了Min-CVCB问题的一个近似算法。该算法具体为：当Min-CVCB问题实例存在受约束最小点覆盖(k<,u>，k<,l>)时，对于任意给定的一个常数s>0，一定可在O((k<,u>+k<,l>)|G|+2<'2/ε>)时间内寻找到一个受约束近似点覆盖(k<,u><'*>，k<,l><'*>)，它满足max{k<,u><'*>/k<,u>，k<,l><'*>/k<,l>}≤1+ε。该算法在理论和实际应用中都具有重要意义。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2问题定义

1.3研究现状

1.4课题研究目标

1.5论文组织

第二章二分图的受约束最小点覆盖问题精确算法

2.1引言

2.2相关参数计算技术、定义和引理

2.2.1核心化技术

2.2.2限定搜索树

2.2.3相关定义和引理

2.3 Min-CVCB问题精确算法

2.3.1减少搜索空间的策略

2.3.2 EACI-dyn算法

2.4 Min-CVCB问题精确算法性能分析

2.5本章小结

第三章二分图的受约束最小点覆盖问题亚指数时间算法

3.1引言

3.2 Min-CVCB问题亚指数时间算法相关概念

3.3 Min-CVCB问题亚指数时间算法

3.3.1分枝搜索

3.3.2动态规划技术

3.4 Min-CVCB问题亚指数时间算法性能分析

3.5 Min-CVCB问题亚指数时间算法存在问题

3.6本章小结

第四章二分图的受约束最小点覆盖问题近似算法

4.1引言

4.2 Min-CVCB问题近似算法相关概念

4.3 Min-CVCB问题PTAS算法

4.3.1预处理操作

4.3.2 AACI-D算法

4.4 Min-CVCB问题近似算法性能分析

4.5本章小结

第五章结束语

5.1研究工作总结

5.2进一步工作

参考文献

致谢

研究成果