| 直线簇上区间图的最小独立控制集 |
| |
| 引用本文： | 皮军德,康丽英,许光俊.直线簇上区间图的最小独立控制集[J].运筹学学报,2006,10(1):107-115. |
| |
| 作者姓名： | 皮军德 康丽英 许光俊 |
| |
| 作者单位： | 1. 河南工业大学理学院,郑州,450052
2. 上海大学数学系,上海200444 |
| |
| 基金项目： | 国家自然科学基金资助课题(10101010)，上海市重点学科建设资助项目和上海市教委青年科学基金资助项目(01QN6262)． |
| |
| 摘 要： | 本文研究了在三种情况下直线上的区间图的最小独立控制集的计算问题:1．相交于一点的直线簇,2．除一条直线外,其余的直线都平行的直线簇,3．一条直线和直线上t个赋权的点,使得其最小独立控制集所覆盖的点的权和最大．本文给出了这三个问题的多项式时间算法,问题1可以在O(n)时间内求解,借助动态规划方法问题2和问题 3分别可以在O(n log n),O(n t)时间内求解．
|
| 关 键 词： | 运筹学 区间图 独立控制集 算法 |
| 收稿时间： | 2004-09-08 |
| 修稿时间： | 2004年9月8日 |
Minimum Independent Dominating Sets of Intervals on Lines |
| |
| Pi Junde,Kang Liying,Xu Guangjun.Minimum Independent Dominating Sets of Intervals on Lines[J].OR Transactions,2006,10(1):107-115. |
| |
| Authors: | Pi Junde Kang Liying Xu Guangjun |
| |
| Institution: | College of Sciences, Henan Univcrsity of Technology, Zhengzhou 450052, China. Department of Mathematics, Shanghai University, Shanghai 200444, China |
| |
| Abstract: | 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. |
| |
| Keywords: | Operations research interval graphs independent dominating set algorithms |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
