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

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

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

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

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E86-D No.11 pp.2390-2394

Publication Date: 2003/11/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithms

Cite this

Copy

Hon-Chan CHEN, Shin-Huei WU, Chang-Biau YANG, "Efficient Algorithms for Finding a Tree 3-Spanner on Permutation Graphs" in IEICE TRANSACTIONS on Information, vol. E86-D, no. 11, pp. 2390-2394, November 2003, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e86-d_11_2390/_p

Copy

@ARTICLE{e86-d_11_2390,
author={Hon-Chan CHEN, Shin-Huei WU, Chang-Biau YANG, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Algorithms for Finding a Tree 3-Spanner on Permutation Graphs},
year={2003},
volume={E86-D},
number={11},
pages={2390-2394},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - Efficient Algorithms for Finding a Tree 3-Spanner on Permutation Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 2390
EP - 2394
AU - Hon-Chan CHEN
AU - Shin-Huei WU
AU - Chang-Biau YANG
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2003
AB - 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.
ER -