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

• 作者: 康丽英 皮军德 许光俊
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 运筹学 区间图 独立控制集 算法
• 年，卷（期）: 2006,（1）
• 页码范围: 107-115
• 页数: 9页
• 分类号: O22
• 字数: 8657字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-6093.2006.01.013

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	康丽英	上海大学数学系	12	14	2.0	2.0
2	许光俊	上海大学数学系	3	2	1.0	1.0
3	皮军德	河南工业大学理学院	11	8	2.0	2.0