Skip to content
Research Article Open access CC BY 3.0

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

Sukumar Mondal

Journal of Scientific Research and Reports · pp. 598–611 · Published 24 Aug 2013

10.9734/JSRR/2013/4661

Abstract

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.

MAD tree spanning tree BFS tree algorithms complexity trapezoid graphs

References (13)

  1. 1 Depth-First Search and Linear Graph Algorithms [DOI]
  2. 2 Algorithmic Graph Theory and Perfect Graphs [DOI]
  3. 3 GRAPH THEORY WITH APPLICATIONS TO ENGINEERING AND COMPUTER SCIENCE [DOI]
  4. 4 The complexity of the network design problem [DOI]
  5. 5 Trapezoid graphs and their coloring [DOI]
  6. 6 A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees [DOI]
  7. 7 Extremal values for ratios of distances in trees [DOI]
  8. 8 Optimal parallel algorithms for problems modeled by a family of intervals [DOI]
  9. 9 AN OPTIMAL ALGORITHM FOR SOLVING ALL-PAIRS SHORTEST PATHS ON TRAPEZOID GRAPHS [DOI]
  10. 10 Dominations in trapezoid graphs [DOI]
  11. 11 MAD trees and distance-hereditary graphs [DOI]
  12. 12 Breadth-first traversal of trees and integer sorting in parallel [DOI]
  13. 13 A linear-time algorithm to compute a MAD tree of an interval graph [DOI]

Cited by 3

Parameterized Algorithms for Computing MAD Trees

Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann · International Workshop on Combinatorial Algorithms · 2026

A survey of the all-pairs shortest paths problem and its variants in graphs

K. Reddy · 2016

Showing 2 of 3 known citations — external sources report more than can currently be individually listed.

Related research

Article metrics

Real usage data collected on this platform.

77

Page views

0

PDF downloads

54

Outbound clicks

3

Citations

Views over time

Views by country

Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".

Traffic sources

Referring site, by host.

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.