论文部分内容阅读
图的控制数理论是图论中一个重要的研究领域,它在计算机科学,通讯科学,网络理论,电力系统,社会学,特别是在计算机网络和通讯系统研究中有着广泛应用。我们称点集S()V为图G=(V,E)的控制集如果对任意的点v∈V-S,总存在S中的一个点与v邻接。图G的控制数γ(G)是图G的控制集的最小基数。在图的控制数理论研究中,算法复杂性研究是一个十分活跃的研究方向,其中一项重要工作是在特殊图类上寻找控制数及其相关参数的有效算法。区间图是一类著名的特殊图类,它形成弦图和完美图的子类,它们在解决很多现实问题中有重要作用。由于区间图具有良好的结构性质,因此许多NP-完全的控制数及其相关参数问题限制在区间图上都是多项式时间可解的。本文主要研究了两类控制参数在区间图上的算法问题,分为两个部分。
第一部分:研究了直线簇上区间图的最小独立控制集和最小连通控制集的求解问题。人们已经证明:许多控制相关参数如独立控制数,连通控制数,全控制数的求解问题,当限制在一条直线上区间图时,基本上都有线性时间算法。本文研究了广义区间图的情况,即多条直线上(直线簇)的区间图的最小独立控制集和最小连通控制集的求解问题。对给定的直线簇上区间图的两个模型,分别给出了求解上述两类问题的多项式时间算法。
第二部分:研究了包含赋权点的区间图的最小独立控制集和最小连通控制集的求解问题。对一条直线上的区间图,其上有n个区间和t个赋权点,要找此区间图的最小独立控制集(最小连通控制集),使得其覆盖的点权和最大。利用动态规划方法,给出了求解此区间图的最大权最小独立控制集和最大权最小连通控制集的多项式时间算法。