10.1184/R1/6703061.v1
Elias Dahlhaus
Elias
Dahlhaus
Peter Dankelmann
Peter
Dankelmann
Ramamoorthi Ravi
Ramamoorthi
Ravi
A Linear-time Algorithm to Compute a MAD Tree of an Interval Graph
Carnegie Mellon University
1979
Graph Algorithms
Interval Graphs
Spanning Tree
1979-06-01 00:00:00
Journal contribution
https://kilthub.cmu.edu/articles/journal_contribution/A_Linear-time_Algorithm_to_Compute_a_MAD_Tree_of_an_Interval_Graph/6703061
The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree.