摘要
給定一個完全圖G跟一些不相交的點集R={R1,R2,...,Rk}，內部史坦納森林的問題就是找一個總重量最輕的史坦納森林，而且在這史坦納森林裡每個點集內的點都要求相互連接且每個R點都不是葉子。若ρ'是史坦納森林問題的一個近似解,m是史坦納森林的連接組件（connected component）的數量，則我們針對內部史坦納森林的問題給予一個2ρ'+4logm的近似解。若k=1，這問題就是內部史坦納樹的問題。ρ是史坦納樹問題的近似解而且之前最好的結果是2ρ+1，我們則給予一個新的近似解2ρ。 此外，如果我們允許最後的圖可能會有循環（cycle）在裡面，也就是不再要求是樹或森林，我們就稱呼這問題是內部史坦納子圖的問題，而且同樣地也給予一個近似解的答案。
並列摘要
Given a complete graph G = (V,E) with metric weight function c : E → R+ and a list R = {R1,R2, ...,Rk} of disjoint vertex subset of V , an internal Steiner forest problem is seek a Steiner forest such that the vertices in Ri are connected with each other and restricted to be internal vertex for this forest. Suppose ρ′ is the approximation ratio for the Steiner forest problem, and m is the number of connected component. we give a approximation ratio 2ρ′ + 4 logm for this problem. If k = 1, this problem is an internal Steiner tree problem, due to Hsieh. Suppose ρ is the approximation ratio for the Steiner tree problem, the previous result of an internal Steiner tree problem is 2ρ + 1 and we also obtain an approximation ratio 2ρ. Moreover, if our result graph allow to have cycle in the above problem, we address this case as internal Steiner subgraph problem and also give an approximation ratio.
參考文獻
延伸閱讀
- Tien, C. L. (2006). 多群組微型仿生體之合作型搜尋演算法發展與行為設計 [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2006.10521
- 陳嘉展（2021）。基於布林運算的多秘密影像分享研究〔碩士論文，淡江大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0002-1708202108502400
- 張基展、胡少華、馮宇廷（2015）。複雜背景下相似融合度背景自動偵測演算法之研究。國防管理學報，36(1)，37-45。https://www.airitilibrary.com/Article/Detail?DocID=10224858-201505-201506150011-201506150011-37-45
- 謝漢欽、鄭祈全、陳燕章（1997）。Building an Expert System for Forest Land Classification。臺灣林業科學，12(3)，255-268。https://doi.org/10.7075/TJFS.199709.0255
- 游惠如（2012）。The Study of Minimum Steiner Tree〔碩士論文，國立虎尾科技大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0028-0307201221293700