上海大学学报（自然科学版）
上海大學學報（自然科學版）
상해대학학보（자연과학판）
JOURNAL OF SHANGHAI UNIVERSITY (NATURAL SCIENCE EDITION)
2005年
6期
600-605
,共6页
区间图%连通控制集%算法
區間圖%連通控製集%算法
구간도%련통공제집%산법
研究了在3种情况下直线上的区间图的最小连通控制集的计算问题:(1)相交于一点的直线簇;(2)除一条直线外,其余的直线都平行的直线簇;(3)一条直线和直线上t个赋权的点,使得其最小连通控制集所覆盖的点的权和最大.给出了这3个问题的多项式时间算法,问题1和问题2可以在O(n)时间内求解,借助动态规划方法问题3可以在O(n+t)时间内求解.
研究瞭在3種情況下直線上的區間圖的最小連通控製集的計算問題:(1)相交于一點的直線簇;(2)除一條直線外,其餘的直線都平行的直線簇;(3)一條直線和直線上t箇賦權的點,使得其最小連通控製集所覆蓋的點的權和最大.給齣瞭這3箇問題的多項式時間算法,問題1和問題2可以在O(n)時間內求解,藉助動態規劃方法問題3可以在O(n+t)時間內求解.
연구료재3충정황하직선상적구간도적최소련통공제집적계산문제:(1)상교우일점적직선족;(2)제일조직선외,기여적직선도평행적직선족;(3)일조직선화직선상t개부권적점,사득기최소련통공제집소복개적점적권화최대.급출료저3개문제적다항식시간산법,문제1화문제2가이재O(n)시간내구해,차조동태규화방법문제3가이재O(n+t)시간내구해.
