中文摘要：

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

英文摘要：

We study the problem of computing minimum independent dominating sets of n intervals on lines in three cases： （1） the lines intersect at a single point, （2） all lines except one are parallel, and （3） one line with t weighted points on it and the minimum independedt dominating set must maximize the sum of the weights of the points covered. we propose polynomial-time algorithms for these problems, the first problem has an O（n）-time solution, while the second and the third problems are solved by dynamic programming algorithms, requiring O（n log n） and （n ＋ t）-time, respectively.