计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2011年
10期
16-22
,共7页
Steiner树%近似算法%精确算法%参数算法
Steiner樹%近似算法%精確算法%參數算法
Steiner수%근사산법%정학산법%삼수산법
Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用.随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT).介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展.最后,提出了该问题的进一步研究方向.
Steiner樹問題是經典的NP難解問題,在計算機網絡佈跼、電路設計以及生物網絡等領域都有很多應用.隨著參數計算理論的髮展,已經證明瞭無嚮圖和有嚮圖中的Steiner樹問題都是固定參數可解的(FPT).介紹瞭無嚮圖和有嚮圖中Steiner樹問題的近似算法和參數算法,分析瞭一些特殊Steiner樹問題的研究現狀,還討論瞭頂點加權Steiner樹問題的研究進展.最後,提齣瞭該問題的進一步研究方嚮.
Steiner수문제시경전적NP난해문제,재계산궤망락포국、전로설계이급생물망락등영역도유흔다응용.수착삼수계산이론적발전,이경증명료무향도화유향도중적Steiner수문제도시고정삼수가해적(FPT).개소료무향도화유향도중Steiner수문제적근사산법화삼수산법,분석료일사특수Steiner수문제적연구현상,환토론료정점가권Steiner수문제적연구진전.최후,제출료해문제적진일보연구방향.
