Skip navigation

DSpace

機構典藏 DSpace 系統致力於保存各式數位資料(如:文字、圖片、PDF)並使其易於取用。

點此認識 DSpace
DSpace logo
English
中文
  • 瀏覽論文
    • 校院系所
    • 出版年
    • 作者
    • 標題
    • 關鍵字
  • 搜尋 TDR
  • 授權 Q&A
    • 我的頁面
    • 接受 E-mail 通知
    • 編輯個人資料
  1. NTU Theses and Dissertations Repository
  2. 電機資訊學院
  3. 資訊網路與多媒體研究所
請用此 Handle URI 來引用此文件: http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43741
標題: 內部史坦納森林之近似演算
Approximating Internal Steiner Forest
作者: Wei-Yang Liu
劉偉揚
指導教授: 呂學一(Hsueh-I Lu)
關鍵字: 史坦納樹,史坦納森林,
Steiner tree,Steiner forest,
出版年 : 2009
學位: 碩士
摘要: 給定一個完全圖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.
URI: http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43741
全文授權: 有償授權
顯示於系所單位:資訊網路與多媒體研究所

文件中的檔案:
檔案 大小格式 
ntu-98-1.pdf
  目前未授權公開取用
225.5 kBAdobe PDF
顯示文件完整紀錄


系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。

社群連結
聯絡資訊
10617臺北市大安區羅斯福路四段1號
No.1 Sec.4, Roosevelt Rd., Taipei, Taiwan, R.O.C. 106
Tel: (02)33662353
Email: ntuetds@ntu.edu.tw
意見箱
相關連結
館藏目錄
國內圖書館整合查詢 MetaCat
臺大學術典藏 NTU Scholars
臺大圖書館數位典藏館
本站聲明
© NTU Library All Rights Reserved