An Efficient Algorithm for Computation of a Minimum Average Distance Tree on Trapezoid Graphs
Journal of Scientific Research and Reports · pp. 598–611 · Published 24 Aug 2013
10.9734/JSRR/2013/4661Abstract
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.
Cited by 2
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann · International Workshop on Combinatorial Algorithms · 2026
Related research
- Evaluation of the Performance of Martial Art Wushu Sportsmen by Measuring the System Complexity — shares topic coverage
- Entropy in the Analysis of Gait Complexity: A State of the Art — shares topic coverage
- Perceived Attributes of Soybean Production Technologies — shares topic coverage
- Area 1 of Approximate Entropy as a Fast and Robust Tool to Address Temporal Organization — shares topic coverage
- Visualizing Climate Change Using Perfect Algorithms — shares topic coverage
Article metrics
Real usage data collected on this platform.
0
Page views
0
PDF downloads
0
Outbound clicks
2
Citations
Views by country
Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".
No views recorded yet.
Traffic sources
Referring site, by host.
No traffic recorded yet.
Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.