一个求外平面图最小顶点赋权反馈点集的线性时间算法

若从一个图中去掉某些顶点后得到的导出子图是无圈图,则所去的那些顶点组成的集合就是原图的反馈点集.本文主要考虑外平面图中的反馈点集并给出了一个求外平面图最小顶点赋权反馈点集的线性时间算法.     

3度图的最小顶点覆盖问题的多项式时间算法

最小顶点覆盖问题是图论和组合数学中经典的NP-Hard问题之一,在实际问题中有着广泛的应用.本文首先给出最小顶点覆盖问题的若干性质,然后根据这些性质设计了3度图最小顶点覆盖问题的一个多项式时间算法,并通过2个实例对算法进行了说明.     

最短时限缺省指派问题的一个解法

将周良泽在1998年提出的最短时限缺省指派问题转化成赋权二分图的最小权K-匹配问题,研究了其解的最优性充分及必要条件,并给出了适合在图上求解的生长树法及适合在表上直接求解的标号法,最后给出一个实例,该算法是一种较简便的算法。     

最短时限缺省指派问题的一种解法

将周良泽在 1998年提出的最短时限缺省指派问题转化成赋权二分图的最小权 K-匹配问题。研究了其解的最优性充分及必要条件 ,并给出了适合在图上求解的生长树法及适合在表上直接求解的标号法 ,最后给出一个实例。该解法是一种较简便的算法。     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

关于区间图的一些有效并行算法

本文基于SIMD-CREW-PRAM一种可同时读但不可同时写的共享计算模型,给出了有关区间图的一些有效的并行算法。如找最大加权集团,最小集团覆盖,等权区间图的最大独立集及最小支配集,真区间图的哈密顿回路及最小带宽。所有这些算法都是最优的,其时间复杂性为O(logn)和处理器数为O(n)。     

直线簇上区间图的最小独立控制集

本文研究了在三种情况下直线上的区间图的最小独立控制集的计算问题:1．相交于一点的直线簇,2．除一条直线外,其余的直线都平行的直线簇,3．一条直线和直线上t个赋权的点,使得其最小独立控制集所覆盖的点的权和最大．本文给出了这三个问题的多项式时间算法,问题1可以在O(n)时间内求解,借助动态规划方法问题2和问题 3分别可以在O(n log n),O(n t)时间内求解．     

瓶颈型Hamming距离下约束最小支撑树的反问题

本文讨论了瓶颈型Hamming距离下约束最小支撑树的反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型Hamming距离来衡量修改的费用,且修改费用最小. 把瓶颈型Hamming距离下约束最小支撑树的反问题转化为最小瓶颈权点覆盖问题,并给出了多项式算法.     

图的部分控制集问题的修正 Greedy算法

部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明。     

网络的分区连接问题

本研究了最小支撑树问题的一个变形——分区连接问题，即对给定的赋权图及其中若干个顶点，求赋权图的权最小支撑森林，使得它的每一个分支恰包含唯一的指定顶点。本给出了该问题的一个时间复杂性为O(|V|^2）的算法。此外，还研究了与该问题的相关的另外三个问题。