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.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0826102-160304 |
| Date | 26 August 2002 |
| Creators | Wu, Shin-Huei |
| Contributors | Hon-Chan Chen, Chang-Biau Yang, Yue-Li Wang, Xuding Zhu |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0826102-160304 |
| Rights | withheld, Copyright information available at source archive |
Page generated in 0.0022 seconds