(3.238.96.184) 您好!臺灣時間:2021/05/08 04:37
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:葉恆青
研究生(外文):Hengchin Yeh
論文名稱:圖論之通報中心問題
論文名稱(外文):Reporting Center Problem for Interval Graphs and Trees
指導教授:李德財李德財引用關係
指導教授(外文):Der-Tsai Lee
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
畢業學年度:92
語文別:英文
論文頁數:56
中文關鍵詞:通報中心問題圖論
外文關鍵詞:Reporting CenterTreeInterval Graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:134
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
In this thesis we have studied the reporting center problem for interval graphs and trees. The reporting center
problem is first introduced in the wireless network field,
in which the reporting center strategy is used as one of the strategies for tracking mobile users, and aims at balancing the cost of updating the user position and the cost of locating a mobile user. The reporting center strategy partitions the cellular network into reporting and non-reporting cells. Associated with each reporting cell is a set of non-reporting cells, called its vicinity.
Mobile users report their position only when they visit a reporting cell.
When a call arrives, the user is searched for only in the vicinity of the last visited reporting center.
The size of the vicinity of a reporting center determines the searching and updating cost of the cellular network.
It is thus an objective to minimize the number of reporting
centers subject to the constraint that the size of the vicinity of each reporting center is bounded by a constant Z>0. The problem has been
shown to be NP-hard for arbitrary graphs
for Z >= 2.
The major contribution of this work is divided into two parts:
(1) an algorithm that solves the reporting center problem for arbitrary vicinity for interval
graphs, thereby improving a previous result which only solves for vicinity Z=2 for interval graphs and for arbitrary vicinity for proper interval graphs, and
(2) an O(n)
time algorithm that solves the reporting center
problem for trees,
which is better than the previous $O(nZ^3)$ result.
1 Introduction 1
2 Reporting Center Problem for Interval Graphs 5
2.1 The Staircase Method 5
2.2 Bricks Transformation Method 28
3 Reporting Center Problem for Trees 31
4.Conclusion 53
5.Bibliography 55
I.F. Akyldiz, J.S.M. Ho,
Dynamic Mobile User Location Update for Wireless PCS Networks,
1 (1995) 187-196.
J.S.M. Ho, I.F.Akyldiz,
Mobile User Location Update and Paging under Delay Constraints,
Wireless Networks 1 (1995) 413-425.

A. Bar-Noy, I. Kessler,
Tracking Mobile Users in Wireless Communications Networks,
IEEE Trans. Inform. Theory 39 (1993) 1877-1886.

A. Bar-Noy, I Kessler, M. Sidi,
Mobile Users: to Update or Not to Update?,
it Wireless Networks 1 (1995) 175-185.

A. Bhattacharya, S.K. Das,
LeZi-Update: An Information Theoretic Approach to Track Mobile Users in PCS Networks,
MobiCom''99, Seattle, 1999.

M.C. Golumbic,
Algorithmic Graph Theory and Perfect Graphs,
Academic Press, New York, 1980.

S. Olariu, M.C. Pinotti, L.Wilson,
Greedy Algorithms for Tracking Mobile Users in Special Mobility Graphs,
Discrete Applied Math. 121 (2002) 215-227.

U. Madhow, M.I. Honig, K. Steiglitz,
Optimization of Wireless Resources for Personcal Communications mobility Tracking,
IEEE/ACM Trans. Networking 3 (1995) 688-707.

C. Rose,
Minimizing the Average Cost of Paging and Registration: a Timer-Based Method,
Wireless Networks 2 (1996) 109-116.

C. Rose, R. Yates,
Minimizing the Average Cost of Paging under Delay Constraints,
Wireless Networks 1 (1995) 211-219.

D.B. West,
Introduction to Graph Theory,
Prentice Hall, Upper Saddle River, 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 劉廣華,〈資訊戰戰區聯盟概念初探〉,《國防通信電子及資訊季刊》,第3期,2002年。
2. 鈕先鍾,〈中共核武發展的評估〉,《國防雜誌》,第11卷第11期,1996年5月。
3. 廖述賢,〈論「電子商務」的興起對國防發展的影響〉,《國防雜誌》,第15卷4期,1999年10月。
4. 廖宏祥,〈台海資訊戰爭的評估與展望〉,《全球防衛雜誌》第180期,1998年8月。
5. 楊念祖,〈中共軍事戰略的演進與未來發展趨勢〉《台北:中國大陸研究》,第42卷10期,1999年10月。
6. 劉福麟,〈中共對『台』的威懾戰略〉,《共黨問題研究》,第23 期,1997年2月。
7. 游豐吉,〈對大陸電信事業發展與改革之研究〉,《中共研究》,第33卷7期,1999年7月。
8. 彭慧鸞,〈資訊時代國際關係理論與實務的研究〉,《問題與研究》(台北),第39卷第5期,2000年5月。
9. 陳偉華,〈從「戰略嚇阻」論台灣「國防戰略」發展的兩難〉,《戰略與國際研究》,第2卷第4期,2000 年10月。
10. 梅林,〈中共超級計算機的發展與運用〉,《中共研究》,第33卷第5期,1999年5月。
11. 張哲銘、翟文中,〈中共發展非對稱軍力對我國國防安全之影響〉,《戰略與國際研究》第1 卷第3期,1999年7月。
12. 康榮平、陳閩,〈中國的高技術產業發展政策以及對外貿影響〉,《當代中國研究》,第3期(總第48期),1995年。
13. 林宗達,〈中共信息戰發展之評估〉,《中共研究》,第36卷第7期,2002年7月。
14. 林宗達,〈中共信息戰略與戰術運用〉,《中華戰略學刊》,2003年,4月。
15. 林文軒,〈淺析中共科技進步與技術創新問題〉,《中共研究》,第34卷第4期,2000年4月。
 
系統版面圖檔 系統版面圖檔