A Linear-time Algorithm to Compute a MAD Tree of an Interval Grap.pdf.pdf' (101.01 kB)

A Linear-time Algorithm to Compute a MAD Tree of an Interval Graph

Download (101.01 kB)
journal contribution
posted on 01.06.1979, 00:00 by Elias Dahlhaus, Peter Dankelmann, Ramamoorthi Ravi
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.

History

Date

01/06/1979

Exports

Exports