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

The average distance(G) of a finite graph 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 is a spanning tree of 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 chapter, I present an efficient algorithm to
compute a minimum average distance spanning tree on trapezoid graphs in time, where is the number
of vertices of the graph.