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   Vol.E86-D    No.11    pp.2390-2394
Publication Date: 2003/11/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithms
tree,  spanner,  permutation graph,  algorithm,  

Full Text: PDF(239.5KB)>>
Buy this Article

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.

open access publishing via