A linear-time algorithm to compute a MAD tree of an interval graph

Elias Dahlhaus; Peter Dankelmann; R. Ravi

doi:10.1016/j.ipl.2003.11.009

A linear-time algorithm to compute a MAD tree of an interval graph

Elias Dahlhaus, Peter Dankelmann, R. Ravi

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	255-259
Number of pages	5
Journal	Information Processing Letters
Volume	89
Issue number	5
DOIs	https://doi.org/10.1016/j.ipl.2003.11.009
Publication status	Published - 16 Mar 2004
Externally published	Yes

Keywords

Graph algorithms
Interval graphs
Spanning tree

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2003.11.009

Cite this

@article{2dc0c416379a4c0db330b4445759ef00,

title = "A linear-time algorithm to compute a MAD tree of an interval graph",

abstract = "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.",

keywords = "Graph algorithms, Interval graphs, Spanning tree",

author = "Elias Dahlhaus and Peter Dankelmann and R. Ravi",

year = "2004",

month = mar,

day = "16",

doi = "10.1016/j.ipl.2003.11.009",

language = "English",

volume = "89",

pages = "255--259",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - A linear-time algorithm to compute a MAD tree of an interval graph

AU - Dahlhaus, Elias

AU - Dankelmann, Peter

AU - Ravi, R.

PY - 2004/3/16

Y1 - 2004/3/16

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

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

KW - Graph algorithms

KW - Interval graphs

KW - Spanning tree

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

U2 - 10.1016/j.ipl.2003.11.009

DO - 10.1016/j.ipl.2003.11.009

M3 - Article

AN - SCOPUS:0742306538

SN - 0020-0190

VL - 89

SP - 255

EP - 259

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

A linear-time algorithm to compute a MAD tree of an interval graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this