顶点覆盖(Vertex Cover)是无向图G=(V,E)的一个顶点子集,使得图G中的任意一条边都至少存在一个顶点属于该子集。最小顶点覆盖问题(Minimum Vertex Cover)的目标是找出包含顶点个数最少的一个顶点覆盖。最小顶点覆盖问题是经典的组合优化问题,与众所周知的最大团、最大独立集、最小支配集等其它难解问题密切相关。此外,最小顶点覆盖问题广泛存在于生物信息学、计算机视觉、网络流量监测、无线通信、电路设计、编码理论等方面,在现实生活中发挥着至关重要的作用。因此,求解最小顶点覆盖问题具有重要的理论指导意义和实际应用价值。目前,求解最小顶点覆盖问题的主流算法以近似算法和精确算法等两类算法为代表。近似算法通常可以在较短的时间内给出质量相对较高的解,但无法证明解质量和搜索效率的稳定性以及解的最优性。而精确算法则没有这个设计缺陷。由于精确算法复杂度较高,因此设计一种高效快速的精确求解算法具有重要意义。本文以分支定界框架作为理论基础,挑选了具有改进算法性能潜力的方向加以研究,本文针对最小顶点覆盖设计的精确算法EMVC在基准算例DIMACS有着优异的表现。来自真实世界的图通常具有非常大的规模,这些图的顶点个数甚至可以达到百万、千万。本文的另一项工作是针对最小顶点覆盖的延伸问题——最小加权顶点覆盖(Minimum Weight Vertex Cover),在大规模图上加以求解。最小加权顶点覆盖问题是在顶点存在权值的情况下,寻找权值之和最小的顶点覆盖。由于顶点存在权值,其求解难度比最小顶点覆盖问题更高。针对于此,本文提出了一种求解大稀疏图中最小加权顶点覆盖问题的精确算法BMWVC。实验表明,BMWVC在约简图规模上取得了明显的效果,可以快速求解真实大规模图。在与目前最好的精确算法,启发式算法对比下,BMWVC毫不逊色,在部分大规模图中,甚至在求解速度上比启发式算法更快,同时解质量达到最优。