Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57382
Title: | 路徑圖上權重備份雙中心問題 The Weighted Backup 2-center Problem on Paths |
Authors: | Ming-Wei Shao 邵明偉 |
Advisor: | 趙坤茂(Kun-Mao Chao) |
Keyword: | 圖論,權重距離,備份雙中心,路徑圖,位置問題, graph theory,weighted distance,backup 2-center,path,location problem, |
Publication Year : | 2014 |
Degree: | 碩士 |
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://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57382 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-103-1.pdf Restricted Access | 573.78 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.