For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Efficient Algorithms for Finding a Tree 3-Spanner on Permutation Graphs
Hon-Chan CHEN Shin-Huei WU Chang-Biau YANG
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/11/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
tree, spanner, permutation graph, algorithm,
Full Text: PDF(239.5KB)>>
A tree 3-spanner T of a graph G is a spanning tree of G such that the distance between any two vertices in T is at most 3 times of their distance in G. Madanlal et al. have presented an O(n + m) time algorithm for finding a tree 3-spanner of a permutation graph. However, the complexity of their algorithm is not optimal, and their algorithm can not be easily parallelized. In this paper, we will propose an improved algorithm to solve the same problem in O(n) time. Moreover, our algorithm can be easily parallelized so that a tree 3-spanner of a permutation graph can be found in O(log n) time with processors on the EREW PRAM computational model.