第三十一卷 第十期 - 2019年十一月十五日 PDF
Counter
部份終端點史坦納樹的近似演算法之改進研究
李佳衛, 黃昭文, 畢文豪, 謝孫源*
國立成功大學資訊工程研究所
 
字體放大
給定一個滿足三角不等式的完全圖G = (V,E,w)，以及子集合R ⊂ V，史坦納樹問題是從G中找出一個包含所有R點且總權重最小的連通子圖。我們研究的部份終端點史坦納樹問題是由經典的史坦納樹問題延伸而來，部份終端點史坦納樹是指包含所有R點且所有給定子集合R'中的點都在樹葉的史坦納樹，而部份終端點史坦納樹問題所求為成本最小的部分終端點史坦納樹，此問題已有多種實際的應用，最常見於IC設計中的最佳化問題。
圖一：部份終端點史坦納樹問題在IC設計上的應用

此問題已知的最佳近似率為2ρ，其中ρ為史坦納樹問題的最佳近似率。
在此論文中，我們提出了近似演算法將近似率由2ρ改進至2ρ-[(ρ)/(3ρ2)]-f，其中f是值在0到ρ-[(ρ)/(3ρ-2)] 之間的函數。
圖二：本研究結果與先前最佳結果的比較
< 上一篇
下一篇 >
Copyright National Cheng Kung University