MAD trees and distance-hereditary graphs

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

doi:10.1016/S0166-218X(02)00422-5

MAD trees and distance-hereditary graphs

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

Research output: Contribution to journal › Conference article › peer-review

7 Citations (Scopus)

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 distance-hereditary graph; that is, those graphs where distances are preserved in every connected induced subgraph.

Original language	English
Pages (from-to)	151-167
Number of pages	17
Journal	Discrete Applied Mathematics
Volume	131
Issue number	1
DOIs	https://doi.org/10.1016/S0166-218X(02)00422-5
Publication status	Published - 6 Sept 2003
Externally published	Yes
Event	2nd International Colloquium - Metz, France Duration: 22 May 2000 → 24 May 2000

Keywords

Distance
Distance-hereditary graphs
Minimum average distance
Spanning tree

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/S0166-218X(02)00422-5

Cite this

@article{24cdbbdc4ae142d0b257599f966199df,

title = "MAD trees and distance-hereditary graphs",

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 distance-hereditary graph; that is, those graphs where distances are preserved in every connected induced subgraph.",

keywords = "Distance, Distance-hereditary graphs, Minimum average distance, Spanning tree",

author = "E. Dahlhaus and P. Dankelmann and W. Goddard and Swart, {H. C.}",

year = "2003",

month = sep,

day = "6",

doi = "10.1016/S0166-218X(02)00422-5",

language = "English",

volume = "131",

pages = "151--167",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1",

note = "2nd International Colloquium ; Conference date: 22-05-2000 Through 24-05-2000",

}

TY - JOUR

T1 - MAD trees and distance-hereditary graphs

AU - Dahlhaus, E.

AU - Dankelmann, P.

AU - Goddard, W.

AU - Swart, H. C.

PY - 2003/9/6

Y1 - 2003/9/6

N2 - 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.

AB - 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.

KW - Distance

KW - Distance-hereditary graphs

KW - Minimum average distance

KW - Spanning tree

UR - http://www.scopus.com/inward/record.url?scp=0042362155&partnerID=8YFLogxK

U2 - 10.1016/S0166-218X(02)00422-5

DO - 10.1016/S0166-218X(02)00422-5

M3 - Conference article

AN - SCOPUS:0042362155

SN - 0166-218X

VL - 131

SP - 151

EP - 167

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

T2 - 2nd International Colloquium

Y2 - 22 May 2000 through 24 May 2000

ER -

MAD trees and distance-hereditary graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this