随着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）时，对于任意给定的一个常数ε＞0，一定可在O(（k_u＋k_l）|G|＋2^2／ε)时间内寻找到一个受约束近似点覆盖（k_u^*，k_l^*），它满足max{k_u^*／k_u，k_l^*／k_l}≤1＋ε。该算法在理论和实际应用中都具有重要意义。