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.