(44.192.10.166) 您好!臺灣時間:2021/03/06 04:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:邵明偉
研究生(外文):Ming-Wei Shao
論文名稱:路徑圖上權重備份雙中心問題
論文名稱(外文):The Weighted Backup 2-center Problem on Paths
指導教授:趙坤茂
指導教授(外文):Kun-Mao Chao
口試委員:王弘倫朱安強
口試委員(外文):Hung-Lun WangAn-Chiang Chu
口試日期:2014-06-20
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:30
中文關鍵詞:圖論權重距離備份雙中心路徑圖位置問題
外文關鍵詞:graph theoryweighted distancebackup 2-centerpathlocation problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:150
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文引用王教授所提出的基於可靠性的備份雙中心模式,在這模式中,每個設施
皆有壞掉機率。我們假設此二設施不會同時壞掉,在這前提下一旦有一設施壞掉,另
一設施需負責所有服務。在路徑圖上具權重的備份雙中心問題中,我們想在點帶權重
之路徑圖上架設此二設施,使得權重距離期望值最小。假設路徑圖上有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.

1 Introduction 1
2 Problem De nition and Notation 4
3 The Weighted Backup 2-center Problem on paths 7
3.1 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Properties of Weighted Backup 2-center . . . . . . . . . . . . . . . . . . . . 9
3.3 The First Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4 Methods for the enhancement . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.5 A Faster Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Conclusion 27
4.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

[1] B. Ben-Moshe, B. Bhattacharya, and Q. Shi. E cient algorithms for the weighted
2-center problem in a cactus graph. In Xiaotie Deng and Ding-Zhu Du, editors,
Algorithms and Computation, Lecture Notes in Computer Science, pages 693{703.
Springer Berlin Heidelberg, 2005.
[2] B. Ben-Moshe, B. Bhattacharya, and Q. Shi. An optimal algorithm for the continuous/
discrete weighted 2-center problem in trees. In Proceedings of the 7th Latin
American Conference on Theoretical Informatics, pages 166{177, 2006.
[3] Y.K. Cheng, L.Y. Kang, and H. Yan. The backup 2-median problem on block graphs.
Acta Mathematicae Applicatae Sinica, English Series, pages 309{320, 2014.
[4] G.N. Frederickson. Parametric search and locating supply centers in trees. In Frank
Dehne, Jorg-Rudiger Sack, and Nicola Santoro, editors, Algorithms and Data Struc-
tures, Lecture Notes in Computer Science, pages 299{319. Springer Berlin Heidelberg,
1991.
[5] G.N. Frederickson and D.B. Johnson. Finding kth paths and p-centers by generating
and searching good data structures. Journal of Algorithms, pages 61{80, 1983.
[6] Y. Hong and L. Kang. Backup 2-center on interval graphs. Theoretical Computer
Science, pages 25{35, 2012.
[7] M. Jeger and O Kariv. Algorithms for nding p-centers on a weighted tree (for
relatively small p). Networks, pages 381{389, 1985.
[8] O. Kariv and S.L. Hakimi. An algorithm approach to network location problems:
part I. the p-centers. SIAM Journal on Applied Mathematics, pages 513{538, 1979.
[9] Y.F. Lan, Y.L. Wang, and H. Suzuki. A linear-time algorithm for solving the center
problem on weighted cactus graphs. Information Processing Letters, pages 205 { 212,
1999.
[10] N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems.
SIAM Journal on Computing, pages 759{776, 1983.
[11] N. Megiddo and A. Tamir. New results on the complexity of p-center problems.
SIAM Journal on Computing, pages 751{758, 1983.
[12] N. Megiddo, A. Tamir, E. Zemel, and R. Chandrasekaran. An O(n log2 n) algorithm
for the kth longest path in a tree with applications to location problems. SIAM
Journal on Computing, pages 328{337, 1981.
[13] L.V. Snyder. Facility location under uncertainty: A review. IIE Transactions, pages
537{554, 2006.
[14] L.V. Snyder and M.S. Daskin. Reliability models for facility location: The expected
failure cost case. Transport Science, pages 400{416, 2005.
[15] A. Tamir. Sorting weighted distances with applications to objective function evaluations
in single facility location problems. Operations Research Letters, pages 249{257,
2004.
[16] H.L. Wang, B.Y. Wu, and K.M. Chao. The backup 2-center and backup 2-median
problems on trees. Networks, pages 39{49, 2009.
[17] B.Y. Wu and K.M. Chao. Spanning Trees and Optimization Problems. CRC Press,
2004.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔