系统科学与数学
繫統科學與數學
계통과학여수학
JOURNAL OF SYSTEMS SCIENCE AND MATHEMATICAL SCIENCES
2008年
11期
1310-1322
,共13页
斯坦纳树问题%区间数据%不确定网络%近似算法
斯坦納樹問題%區間數據%不確定網絡%近似算法
사탄납수문제%구간수거%불학정망락%근사산법
考虑了在带区间数据的不确定网络中.最小风险和模型以及最小最大风险模型下的斯坦纳树问题.它们推广了相应模型下的最短路问题和最小支撑树问题,在网络设计中具有更加广泛的应用.我们分别给出了这两个模型下斯坦纳树问题的近似算法,并对算法性能做了理论分析和证明.结果显示我们的算法具有优良的常数逼近的性质,能在多项式时间内算出令人满意的解.
攷慮瞭在帶區間數據的不確定網絡中.最小風險和模型以及最小最大風險模型下的斯坦納樹問題.它們推廣瞭相應模型下的最短路問題和最小支撐樹問題,在網絡設計中具有更加廣汎的應用.我們分彆給齣瞭這兩箇模型下斯坦納樹問題的近似算法,併對算法性能做瞭理論分析和證明.結果顯示我們的算法具有優良的常數逼近的性質,能在多項式時間內算齣令人滿意的解.
고필료재대구간수거적불학정망락중.최소풍험화모형이급최소최대풍험모형하적사탄납수문제.타문추엄료상응모형하적최단로문제화최소지탱수문제,재망락설계중구유경가엄범적응용.아문분별급출료저량개모형하사탄납수문제적근사산법,병대산법성능주료이론분석화증명.결과현시아문적산법구유우량적상수핍근적성질,능재다항식시간내산출령인만의적해.
