对于NP难问题来说,精确的指数时间算法是算法领域一个重要的研究课题,特别是在某些情况下近似算法难以满足计算的需求。在设计这一类算法的时候,最常见的是Davis Putnam所提出的搜索树算法,即分支约减算法。该方法通过将问题分解为子问题并递归求解最终得到计算结果。为了提高算法的速度,研究者在设计分支约减算法的时候加入越来越复杂的约减规则,以使问题实例在分解前能够尽量简化,这导致算法的实现常常变得冗繁和困难。而与此同时,分支约减算法的分析方法却并没有大的改进,问题实例规模的测度往往比较简单,这使得对算法时间复杂度的分析不够精确,从而无法得到比较紧的算法运行时间上界。Fomin等人最近提出了一种称为度量与分治(measure and conquer)的技术,通过对问题实例规模的不同组成部分加权来更精确的刻画问题实例,以获得对分支约减算法更准确的分析。本文以此为切入点,以最小支配集问题为例,全面介绍了度量与分治方法的概念、方法和算法分析过程。除此之外,本文还将度量与分治方法应用在了分支约减算法的设计当中。论文的主要内容包括：·本文以最小集合覆盖的分支约减算法为例,基于Fomin的分析系统阐释了使用度量与分治方法设计加权度量、分析子问题规模、优化权值以及获得算法时间复杂度的具体过程,并证明了Grandoni的算法在使用多项式空间和指数空间的情况下,分别可以在O(1.5260n)和O(1.5161n)时间内解决最小支配集问题。·本文修正了Fomin在最初使用度量与分治方法对算法进行分析时的一个缺陷,并详细说明了错误的原因,给出了修正的方法。·本文对度量与分治分析过程中得到的算法最坏情况进行了研究,并基于此设计了新的相对简单的约减规则,从而重新设计和改进了算法。最终证明了新算法可以在使用使用多项式空间和指数空间的情况下,分别在O(1.5152n)和O(1.5105n)时间内解决最小支配集问题。·本文研究了度量与分治方法中权值优化所使用的拟凸规划(quasiconvex programming)方法,讨论了该方法应用在度量与分治方法中所需要解决的问题。本文还修改了Eppstein提出的平滑拟凸规划(smooth quasiconvex programming)算法,使之能够更有效的解决度量与分治方法中的权值优化问题。本文从提高算法分析准确性的角度研究了基于分支约减技术的精确指数时间算法的分析与设计,以最小支配集问题为例讨论了度量与分治方法,并给出了已有算法更紧的上界。此外,本文还利用分析结果将度量与分治方法应用于算法设计当中,通过设计新的约减规则改进了算法。