An Efficient Algorithm for Computation of a Minimum Average Distance Tree on Trapezoid Graphs
Theory and Applications of Mathematical Science Vol. 2,
Page 58-70
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.
Keywords:
- MAD tree
- spanning tree
- BFS tree
- algorithms
- complexity
- trapezoid graphs
How to Cite
- Abstract View: 0 times