Efficient Algorithms for Finding a Tree 3-Spanner on Permutation Graphs

Hon-Chan CHEN  Shin-Huei WU  Chang-Biau YANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.11   pp.2390-2394
Publication Date: 2003/11/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithms
Keyword: 
tree,  spanner,  permutation graph,  algorithm,  

Full Text: PDF>>
Buy this Article




Summary: 
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.