# 臺灣博碩士論文加值系統

(3.235.140.84) 您好！臺灣時間：2022/08/15 03:29

:::

### 詳目顯示

:
 Twitter

• 被引用:0
• 點閱:204
• 評分:
• 下載:0
• 書目收藏:0
 在這篇論文中,我們先介紹了一個演算法來找出梯形圖上的4-拓展樹,接著介紹了一個在排列圖上改良過後的3-拓展樹, 然後我們依據這個演算法作雛形, 在梯形圖來找出邊數最多為2n 的拓展者, 最後我們提出一個反證證明 區間圖上沒有2-拓展樹. 至於複雜度方面,找出梯形圖的4-拓展樹為 O(n), 在排列圖上改良過後的3-拓展樹為O(n)(原來是O(m + n)) ,在梯形圖找出邊數最多為2n 的拓展者為O(n)
 A t-spanner of a graph G is a subgraph H of G, which the distance between any two vertices in H is at most t times their distance in G. A tree t-spanner of G is a t-spanner which is a tree. In this dissertation, we discuss the t-spanners ontrapezoid, permutation, and interval graphs. We ﬁrst introduce an O(n) algorithm for ﬁnding a tree 4-spanner on trapezoid graphs. Then, give an O(n)algorithm for ﬁnding a tree 3-spanner on permutation graphs, improving the existed O(n + m)algorithm. Since the class of permutation graphs is a subclass of trapezoid graphs, we can apply the algorithm on permutation graphs to ﬁnd the approximation of a tree 3-spanner on trapezoid graphs in O(n) time with edge bound 2n. Finally, we show that not all interval graphs have a tree 2-spanner.
 ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2. Permutation, Interval, and Trapezoid Graphs . . . . . . . 4Chapter 3. Tree 4-Spanners on Trapezoid Graphs . . . . . . . . . . . 93.1 Prelimiaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2 Ekkehard’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3 Finding a Tree 4-spanner of a Trapezoid Graph . . . . . . . . . . . . 123.4 The Correctness of Algorithm3.B . . . . . . . . . . . . . . . . . . . . 153.5 Implementing Algorithm 3.B in O(n) Time . . . . . . . . . . . . . . . 25Chapter 4. Tree 3-Spanners on Permutation Graphs . . . . . . . . . . 324.1 Madanlal’s Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 324.2 An O(n) Algorithm for Finding a Tree 3-spanner . . . . . . . . . . . 344.3 The Correctness of Algorithm4.B . . . . . . . . . . . . . . . . . . . . 36Chapter 5. Finding a 3-spanner of Edge Bound 2n on Trapezoidgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.1 Finding a 3-spanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.2 The Correctness of Algorithm5.A . . . . . . . . . . . . . . . . . . . . 43PageChapter 6. Tree t-spanners on Interval Graphs . . . . . . . . . . . . . 456.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.2 An Example of One Interval Graph Without Having Tree 2-spanner . . . 46Chapter 7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
 [1] S. Arikati, D. Chen, L. P. Chew, G. Das, M. Smid, and D. Zaroliagis, “Plannarspanners and approximate shortest path queries among obstacles in the plane,”in:J.Diaz(ED.), Algorithm-ESA ’96, Springer Lecture Notes in Computer Science,Vol. 1136, pp. 399—407, 1996.[2] K. Arvind and C. P. Rangan, “Connected domination and steiner set onweighted permutation graphs,” Infornation Processing Letters, Vol. 41, pp. 215—220, 1992.[3] V. Bojarshinov, “Edge and total coloring of interval graphs,” Discrete AppliedMathematics, Vol. 14, pp. 23—28, 2001.[4] A. Brands¨adt and F. Krash, “On domination problems for permutatiob andother graphs,” Theoretical Computer Science, Vol. 54, pp. 181—198, 1987.[5] L. Cai and D. G. Corneil, “Tree spanners,” SIAM Journal on Discrete Mathmatics,Vol. 8, pp. 359—387, 1995.[6] Chang, Maw-Shang, Nagavamsi, P., Rangan, and C. Pandu, “Weighted irredundanceof interval graphs,” Information Processing Letters, pp. 65—70, 1998.[7] L. P. Chew, “There is a plannar graph almost as good as the completegraph,” Proceeding of the Second ACM symposium on Computational Geometry,pp. 399—407, 1996.[8] C. J. Colbourn and L. K. Stewart, “Permutation graphs: Connected dominationand steiner trees,” Discrete Applied Mathmatics, pp. 179—189, 1990.[9] D. Corneil and P. Kamula, “Extension of permutation and interval,” Proceedingof the 18th Southeast. Coference on Combinatorics, Graph Theoy, and Compuing,BocaRatonm FL; Congressus Numerantium, Vol. 58, pp. 267—275, 1987.[10] I. Dagan, M. C. GOLUMBIC, and R. Y. Pinter, “Trapezoid graphs and theircoloring,” Discrete Applied Mathmatics, Vol. 21, pp. 97—102, 1988.49[11] D. P. Dobkin, S. J. Friedman, and K. J. Supowit, “Delaunay graphs are asalmost good as complete graphs,” Discrete & Computational Geometry, Vol. 15,pp. 399—407, 1990.[12] W. Duckworth and M. Zito, “Sparse hypercube 3-spanners,” Discrete AppliedMathmatics, Vol. 59, pp. 289—295, 2000.[13] M. Farber and j. M. Keil, “Domination in permutation graphs,” Journal ofAlgorithms, Vol. 16, pp. 453—469, 1994.[14] M. C. Golumbic, Algorithm Graph Theory and Perfect Graphs. New York:Academic Press, 1980.[15] J. Y. Hsiao and C. Y. Tang, “An ecent algorithm for nding a maximumweight 2-independent set on inerval graphs,” Information Processing Letters,Vol. 43, pp. 229—235, 1992.[16] k¨ohler, “Connected dominating clique in trapezoid graph,” Discrete AppliedMathmatics, Vol. 99, pp. 91—110, 2000.[17] Y. D. Ling, “Domination in trapezoid grpahs,” Infornation Processing Letters,Vol. 52, pp. 309—315, 1994.[18] Y. D. Ling, “Steiner set and connected domination,” Infornation ProcessingLetters, Vol. 56, pp. 101—108, 1996.[19] Y. D. Ling, C. Rhee, S. K. Dall, and S. Lakashmivarahan, “A new approachfor teh domination problem on permutation graphs,” Infornation ProcessingLetters, Vol. 37, pp. 219—224, 1991.[20] M. S. Madanlal, G. Venkatesan, and C. P. Rangan, “Tree 3-spanners on interval,permutation and regular bipartite graphs,” Infornation Processing Letters,pp. 97—102, 1996.[21] D. Peleg and A. A. Sch¨aer, “Graph spanners,” Congressus Numberantium,Vol. 13, pp. 329—343, 1982.[22] D. Peleg and J. Ullman, “An optimal synchronizer for the hypercube,” Proceedingof the 6th ACM Symoisium on Principles of Distributed Computing,pp. 77—85, 1987.[23] G. Ramalingam and C. P. Rangan, “A unied approach to domination problemson interval graphs,” Infornation Processing Letters, Vol. 27, pp. 271—274, 1988.50[24] C. Rhee, Y. D. Ling, S. K. Dhall, and S. Lakashmivarahan, “An o(n+m) algorithmfor nding minimum weight dominating set in permutation graphs,”SIAM Journal on Computing, Vol. 25(2), pp. 404—419, 1996.[25] J. Soares, “Graph spanners: a survey,” Congressus Numerantium, Vol. 89,pp. 225—238, 1992.[26] K. H. Tsai and W. L. Hsu, “Fast algorithm for the dominating set problem onpermutation graphs,” Algorithmuca, Vol. 9, pp. 601—614, 1993.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 最小分級生成樹問題之研究 2 有關有界容錯圖形、比較性圖形之補圖和弱有弦圖的一些結果 3 在排列圖及區間圖上一些問題的平行演算法設計及分析

 無相關期刊

 1 利用曲線對齊之蛋白質結構預測方法 2 可使用於MPEG-4之新的畫面內與畫面間模式下的形狀編碼演算法 3 對於IEEE802.11無線區域網路提出考量能量消耗的輪詢機制 4 HTML/WML自動轉譯之研究 5 一個以藍芽路由通訊協定所架構的AdHoc網路 6 在Adhoc無線通訊網路上利用競爭方式的廣播通訊協定 7 適用於低成本嵌入式應用之多媒體微控制器 8 在叢集式伺服器上設計與實作一個以硬體為基礎的封包轉送機制 9 分散式網頁伺服器行動管理系統之設計與實作 10 利用DNA設計生物電腦的排序器 11 課堂外的風景─談表演藝術課程之創辦與營運 12 從虛實整合創新探討互聯網+旅遊模式以智慧旅遊為例 13 炭化活化設備的營運模式研究 14 基於混合式基數字組式蒙哥馬利模數乘法演算法之RSA密碼演算法硬體架構 15 半導體設備離子佈植機－作業人員機台清潔時砷暴露健康風險探討

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室