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.0021 seconds