运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2006年
1期
107-115
,共9页
运筹学%区间图%独立控制集%算法
運籌學%區間圖%獨立控製集%算法
운주학%구간도%독립공제집%산법
本文研究了在三种情况下直线上的区间图的最小独立控制集的计算问题: 1.相交于一点的直线簇,2.除一条直线外,其余的直线都平行的直线簇,3.一条直线和直线上t个赋权的点,使得其最小独立控制集所覆盖的点的权和最大.本文给出了这三个问题的多项式时间算法,问题1可以在O(n)时间内求解,借助动态规划方法问题2和问题3分别可以在O(nlogn),O(nt)时间内求解.
本文研究瞭在三種情況下直線上的區間圖的最小獨立控製集的計算問題: 1.相交于一點的直線簇,2.除一條直線外,其餘的直線都平行的直線簇,3.一條直線和直線上t箇賦權的點,使得其最小獨立控製集所覆蓋的點的權和最大.本文給齣瞭這三箇問題的多項式時間算法,問題1可以在O(n)時間內求解,藉助動態規劃方法問題2和問題3分彆可以在O(nlogn),O(nt)時間內求解.
본문연구료재삼충정황하직선상적구간도적최소독립공제집적계산문제: 1.상교우일점적직선족,2.제일조직선외,기여적직선도평행적직선족,3.일조직선화직선상t개부권적점,사득기최소독립공제집소복개적점적권화최대.본문급출료저삼개문제적다항식시간산법,문제1가이재O(n)시간내구해,차조동태규화방법문제2화문제3분별가이재O(nlogn),O(nt)시간내구해.
