Additive tree 2-spanners of permutation graphs

Abstract

Let G be a connected graph. A spanning tree T of G is a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. If their distances in T and G differ by at most t, then T is an additive tree t-spanner of G. In this paper, we show that any permutation graph has an additive tree 2-spanner, and it can be found in O(n) time sequentially or in O(log n) time with O(n/log n) processors on the EREW PRAM computational model by using a previously published algorithm for finding a tree 3-spanner of a permutation graph.

Keywords:

• spanner
• permutation graph
• algorithm

CCS Category :

• F.2.2
• G.2.2

Acknowledgements

The authors would like to thank the anonymous referees for their helpful suggestions.