請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8468
標題: | 在加權樹上基於郵政模型的廣播雙中心問題 The Broadcasting 2-Center Problem in Weighted Trees under the Postal Model |
作者: | Chan-Hung Hsu 徐展鴻 |
指導教授: | 陳健輝(Gen-Huey Chen) |
關鍵字: | 廣播問題,雙中心,郵政模型,合成函數, broadcasting problem,2-center,postal model,function composition, |
出版年 : | 2020 |
學位: | 碩士 |
摘要: | 廣播問題是在給定的圖中找尋廣播起始點,使得圖上最長通訊時間最小化。在本篇論文中,我們考慮加權樹上基於郵政模型的廣播問題。對於單中心的廣播問題,Su, Lin, and Lee 提出了線性時間複雜度的演算法。本篇論文更進一步提出線性時間複雜度的演算法,將其結果延伸到廣播雙中心問題。 我們觀察到廣播過程中會存在一條未使用到的邊,並證明最佳解中未使用到的邊會落在一條特定的路徑上。接著利用相鄰子樹的重疊性質減少重複計算,計算該路徑上每個邊兩側子樹的廣播時間,以找出廣播雙中心的位置。 We consider the broadcasting 2-center problem in weighted trees under the postal model in this thesis. We observe that there is always an edge not used during the broadcast process. Further, we prove that the unused edge in the optimal solution will lie on a specific path structure. By computing all the broadcast time for subtrees in the both side of each edge on the path, we propose an O(n) time algorithm for solving the broadcasting 2-center problem. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8468 |
DOI: | 10.6342/NTU202001303 |
全文授權: | 同意授權(全球公開) |
電子全文公開日期: | 2023-08-01 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-0307202018184000.pdf | 1.11 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。