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