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

Abstract

The average distance  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.