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