| MAD trees and distance-hereditary graphs (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| 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 distancehereditary graph; that is, those graphs where distances are preserved in every connected induced subgraph. | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||