覆盖问题是计算几何和组合优化领域中的一类重要的难解问题,对此类问题的研究不但具有重大的理论意义,而且在生物计算、电路设计、网络选址、工艺流程分析等应用领域具有许多重要的实际意义。人们从实际应用中抽象出了许多的覆盖问题,如顶点覆盖问题、树覆盖问题、超平面覆盖问题、集合覆盖问题等。本文主要对超平面覆盖问题和基于保证值的完美匹配图中顶点覆盖问题进行了深入的研究。对于超平面覆盖问题,本文首先通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征,提出了一个时间复杂度为O*((0.736k)k)勺的确定性的参数算法,较大地改进了以前最好的时间复杂度为O*((k/2.2)2k)勺的算法。更一般地,我们还提出了关于超平面覆盖问题的确定性的参数算法,其时间复杂度为O*((dk)!/((d!)kk!)),较之前的时间复杂度为O*(kd(k+1))的算法亦有较大改进。对于完美匹配图中基于保证值的顶点覆盖问题,已有相关文献提出了一个时间复杂度为O*(15k)勺的固定参数算法。本文对此算法作了进一步的改进,其整体思路是首先采用迭代压缩技术将原问题转化为求一个特殊的具有完美匹配的Konig图上的最小顶点覆盖问题,然后将后者进一步转化为参数化2-ASLASAT问题的一个变种问题(KPM-2-AASAT问题),最后,通过深入分析问题的结构特征,我们采用分枝搜索技术和隐含参数技术求解KPM-2-AASAT问题。整个算法的时间复杂度为O*(9勺,较之前最好结果有较大改进。本文最后对上述两个问题的研究工作进行了总结,并对今后的相关研究工作做了简要的阐述。