直线簇上区间图的最小连通控制集

摘要：

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

关键词：区间图、连通控制集、算法

所属期刊栏目：11

分类号：O157.5(代数、数论、组合理论)

资助基金：中国科学院资助项目10101010;上海市学科建设项目;上海市教委资助项目01QN6262

在线出版日期：2006-03-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：600-605