簡易檢索 / 詳目顯示
| 研究生： |
陳政謙 Cheng-Chien Chen |
|---|---|
| 論文名稱： |
極大外平面圖上之距離監視問題 Distance Guarding Problem in Maximal Outerplanar Graphs |
| 指導教授： |
王有禮
Yue-Li Wang |
| 口試委員: |
徐俊傑
Chiun-Chieh Hsu 吳若禹 Ro-Yu Wu |
| 學位類別： |
碩士 Master |
| 系所名稱： |
管理學院 - 資訊管理系 Department of Information Management |
| 論文出版年： | 2016 |
| 畢業學年度： | 104 |
| 語文別： | 英文 |
| 論文頁數： | 22 |
| 中文關鍵詞： | 距離k監視問題 、距離k監視集合 、極大外平面圖 |
| 外文關鍵詞： | kd-guarding problem, kd-guarding set, maximal outerplanar graphs |
| 相關次數： | 點閱：150 下載：1 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
給定一個平面圖G,圖G上的一個內平面f 可以被一個點p距離k可見的條件為點p到平面f 的 邊界上一點x的距離小於等於k − 1。 一組在圖G上的距離k監視集合S為一組點集合使得圖G上 的每一個內平面都可以被S集合中的點距離k可見。 在本篇論文中,我們設計了一個線性時間 的演算法在極大外平面圖上找最小之距離2監視集合。
Given a planar graph G = (V, E), we say that an inner face f of G is kd-visible from a vertex p ∈ V if there is a vertex x in the boundary of f such that dG(x,p) k − 1, where dG(p,x) is the length of a shortest path from p to x. A kd-guarding set of G is a subset S ⊆ V such that every face of G is kd-visible from some vertex in S. In this thesis, we show that finding a minimal 2d-guarding set of a maximal outerplanar graph can be solved in linear time.
[1] J.D. Alvarado, S. Dantas, D. Rautenbach, Distance k-domination, distance k-guarding, and distance k-vertex cover of maximal outerplanar graphs, Discrete Applied Mathematics 194 (2015) 154–159.
[2] P. Bose, T. Shermer, G. Toussaint, B. Zhu, Guarding polyhedral terrains, Computational Geometry 7(3) (1997) 173–185.
[3] C.N. Campos, Y. Wakabayashi, On dominating sets of maximal outerplanar graphs, Discrete Applied Mathematics 161(3) (2013) 330–335.
[4] S. Canales, G. Hernandez, M. Martins and I. Matos, Distance domination, guarding and covering of maximal outerplanar graphs, Discrete Applied Mathematics 181 (2015) 41–49.
[5] V. Chv ́atal, A combinatorial theorem in plane geometry, Journal of Combinatorial Theory, Series B 18(1) (1975) 39–41.
[6] S. Fisk, A short proof of Chv ́atal’s Watchman Theorem, Journal of Combinatorial Theory, Series B 24(3) (1978) 374.
[7] L.R. Matheson, R.E. Tarjan, Dominating Sets in Planar Graphs, European Journal of Com- binatorics 17(6) (1996) 565–568.
[8] I. Salleh, K-vertex guarding simple polygons, Computational Geometry 42(4) (2009) 352– 361.
[9] T. Shermer, Covering and guarding polygons using Lk-sets, Geometriae Dedicata 37(2) (1991) 183–203.
[10] S. Tokunaga, Dominating sets of maximal outerplanar graphs, Discrete Applied Mathemat- ics 161(18) (2013) 3097–3099.
