https://scholars.lib.ntu.edu.tw/handle/123456789/118981
Title: | 路徑圖上權重備份雙中心問題 The Weighted Backup 2-center Problem on Paths |
Authors: | 邵明偉 Shao, Ming-Wei |
Keywords: | 圖論;權重距離;備份雙中心;路徑圖;位置問題 | Issue Date: | 2014 | Abstract: | 本論文引用王教授所提出的基於可靠性的備份雙中心模式,在這模式中,每個設施 皆有壞掉機率。我們假設此二設施不會同時壞掉,在這前提下一旦有一設施壞掉,另 一設施需負責所有服務。在路徑圖上具權重的備份雙中心問題中,我們想在點帶權重 之路徑圖上架設此二設施,使得權重距離期望值最小。假設路徑圖上有n個點,我們 建立了一個時間複雜度為O(n)的演算法。 In this thesis, we apply the reliability-based backup 2-center model proposed by Wang, where each facility may fail with a given probability. Once a facility fails, the other has to be responsible for all the services. We assume that two facilities do not fail at the same time. In the weighted backup 2-center problem on paths, we want to locate two facilities on vertex-weighted paths such that the expected weighted distance is minimized. We construct an O(n)-time algorithm, where n is the number of vertices in the given path. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/261546 | Rights: | 論文公開時間:2014/08/01 論文使用權限:同意有償授權(權利金給回饋學校) |
Appears in Collections: | 資訊工程學系 |
File | Description | Size | Format | |
---|---|---|---|---|
ntu-103-R01922128-1.pdf | 23.32 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.