A linear time algorithm to construct a tree 4-spanner on trapezoid graphs

Abstract

In a graph G, a spanning tree T is said to be a tree t-spanner of the 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 networks and distributed environments. In this paper, we present an algorithm to find a tree 4-spanner on trapezoid graphs in O(n) time, where n is the number of vertices.

Keywords:

• design of algorithms
• analysis of algorithms
• shortest paths
• tree t-spanner
• trapezoid graphs

2000 AMS Subject Classification :

• 68Q22
• 68Q25
• 68R10

Acknowledgements

The authors are grateful to the referee for his/her suggestions in improving the quality and presentation of the paper.