MAD trees and distance-hereditary graphs

E. Dahlhaus, P. Dankelmann, W. Goddard, H. C. Swart

Research output: Contribution to journalConference articlepeer-review

7 Citations (Scopus)


For a graph G with weight function w on the vertices, the total distance of G is the sum over all unordered pairs of vertices x and y of w(x)w(y) times the distance between x and y. A MAD tree of G is a spanning tree with minimum total distance. We develop a linear-time algorithm to find a MAD tree of a distance-hereditary graph; that is, those graphs where distances are preserved in every connected induced subgraph.

Original languageEnglish
Pages (from-to)151-167
Number of pages17
JournalDiscrete Applied Mathematics
Issue number1
Publication statusPublished - 6 Sept 2003
Externally publishedYes
Event2nd International Colloquium - Metz, France
Duration: 22 May 200024 May 2000


  • Distance
  • Distance-hereditary graphs
  • Minimum average distance
  • Spanning tree

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'MAD trees and distance-hereditary graphs'. Together they form a unique fingerprint.

Cite this