AT-free图的配对控制集算法

本文给出了配对控制集在AT-free图的BFS-树上分布的结构性质．利用这些性质，我们给出了求解AT-free图类最小配对控制集的多项式时间算法．     

四阶不完全对称张量M-特征值的新包含域及应用

四阶不完全对称张量的M-特征值在非线性弹性材料分析中有着广泛的应用.本文的目的是给出四阶不完全对称张量M-特征值的新包含域,得到最大M-特征值上界更精确的估计,并将得到的上界估计值应用到计算最大M-特征值的WQZ算法中,数值例子验证了结果的有效性.最后,基于得到的包含域,给出了四阶不完全对称张量正定性判定的充分条件.     

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

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