An Efficient Algorithm for Computation of a Minimum Average Distance Tree on Trapezoid Graphs

The average distance μ(G) of a finite graph G = (V, E) is the average of the distances over all unordered pairs of vertices which can be used as a tool in analytic networks where the performance time is proportional to the distance between any two nodes. A minimum average distance spanning tree of G is a spanning tree of G with minimum average distance. Such a tree is sometimes referred to as a minimum routing cost spanning tree and these are of interest in the design of communication networks. In this paper, I present an efficient algorithm to compute a minimum average distance spanning tree on trapezoid graphs in O(n2) time, where n is the number of vertices of the graph.