跳到主要內容

臺灣博碩士論文加值系統

(3.235.140.84) 您好!臺灣時間:2022/08/15 03:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳信輝
研究生(外文):Shin-Huei Wu
論文名稱:區間圖、排列圖及梯形圖上的t-擴展樹
論文名稱(外文):Finding Tree t-spanners on Interval, Permutation and Trapezoid Graphs
指導教授:楊昌彪楊昌彪引用關係
指導教授(外文):Chang-Biau Yang
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:51
中文關鍵詞:排列圖及梯形圖上的t-擴展樹區間圖
外文關鍵詞:permutation graphsinterval graphstrapezoid graphst-spanner
相關次數:
  • 被引用被引用: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 on
trapezoid, permutation, and interval graphs. We first introduce an O(n) algorithm for finding a tree 4-spanner on trapezoid graphs. Then, give an O(n)algorithm for finding 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 find 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0
Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 2. Permutation, Interval, and Trapezoid Graphs . . . . . . . 4
Chapter 3. Tree 4-Spanners on Trapezoid Graphs . . . . . . . . . . . 9
3.1 Prelimiaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Ekkehard’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Finding a Tree 4-spanner of a Trapezoid Graph . . . . . . . . . . . . 12
3.4 The Correctness of Algorithm3.B . . . . . . . . . . . . . . . . . . . . 15
3.5 Implementing Algorithm 3.B in O(n) Time . . . . . . . . . . . . . . . 25
Chapter 4. Tree 3-Spanners on Permutation Graphs . . . . . . . . . . 32
4.1 Madanlal’s Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2 An O(n) Algorithm for Finding a Tree 3-spanner . . . . . . . . . . . 34
4.3 The Correctness of Algorithm4.B . . . . . . . . . . . . . . . . . . . . 36
Chapter 5. Finding a 3-spanner of Edge Bound 2n on Trapezoid
graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.1 Finding a 3-spanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 The Correctness of Algorithm5.A . . . . . . . . . . . . . . . . . . . . 43
Page
Chapter 6. Tree t-spanners on Interval Graphs . . . . . . . . . . . . . 45
6.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.2 An Example of One Interval Graph Without Having Tree 2-spanner . . . 46
Chapter 7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top