An optimal parallel algorithm to construct a tree 3-spanner on interval graphs

Abstract

A spanning tree T is said to be a tree t-spanner of a graph G if the distance between any two vertices in T is at most t times their distance in G. The tree t-spanner has many applications in network and distributed environments. This problem is NP-hard for general graph even for some special classes of graphs. This problem is polynomial solvable for interval graph when t ≥ 3. When t = 2 the exact complexity of the problem still remains open, but, for t = 2 a polynomial time 2-approximation algorithm is available. An O(n + m) time sequential algorithm is available to solve tree 3-spanner problem, where m and n, respectively, represent the number of edges and the number of vertices of the interval graph. Here, a parallel algorithm is designed to solve a tree 3-spanner problem in O(log n) time using O (n/log n) processors on an EREW PRAM. As a byproduct, a parallel algorithm is also designed to find the increasing sequence of numbers of a set of N numbers in O (log N) time using O(N/log N) processors.

Keywords:

• Parallel algorithms
• Design and analysis of algorithms
• t-Spanner
• Tree t-spanner
• Interval graph

Acknowledgements

This research work of second author is partially supported by the Department of Science and Technology, Government of India, under grant number SR/FTP/ETA-008/2002.