On average edge length of minimum spanning trees

Suman Kumar Nath; Rezaul Alam Chowdhury; M. Kaykobad

doi:10.1016/S0020-0190(99)00068-X

On average edge length of minimum spanning trees

Suman Kumar Nath
, Rezaul Alam Chowdhury
, M. Kaykobad

Computer Science

Bangladesh University of Engineering and Technology

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

Abstract

A theorem that asserts that average edge length of the minimum tree of a complete graph on n+1 vertices is less than or equal to the average length of all the n+1 minimum spanning trees of the induced graph on n vertices is presented. The theorem generalizes the result for any graph without any constraints.

Original language	English
Pages (from-to)	241-243
Number of pages	3
Journal	Information Processing Letters
Volume	70
Issue number	5
DOIs	https://doi.org/10.1016/S0020-0190(99)00068-X
State	Published - Jun 21 1999

Access to Document

10.1016/S0020-0190(99)00068-X

Cite this

@article{0e1c925cfdc749a6a8bb73c800b1e6e6,

title = "On average edge length of minimum spanning trees",

abstract = "A theorem that asserts that average edge length of the minimum tree of a complete graph on n+1 vertices is less than or equal to the average length of all the n+1 minimum spanning trees of the induced graph on n vertices is presented. The theorem generalizes the result for any graph without any constraints.",

author = "Nath, \{Suman Kumar\} and Chowdhury, \{Rezaul Alam\} and M. Kaykobad",

year = "1999",

month = jun,

day = "21",

doi = "10.1016/S0020-0190(99)00068-X",

language = "English",

volume = "70",

pages = "241--243",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "5",

}

TY - JOUR

T1 - On average edge length of minimum spanning trees

AU - Nath, Suman Kumar

AU - Chowdhury, Rezaul Alam

AU - Kaykobad, M.

PY - 1999/6/21

Y1 - 1999/6/21

N2 - A theorem that asserts that average edge length of the minimum tree of a complete graph on n+1 vertices is less than or equal to the average length of all the n+1 minimum spanning trees of the induced graph on n vertices is presented. The theorem generalizes the result for any graph without any constraints.

AB - A theorem that asserts that average edge length of the minimum tree of a complete graph on n+1 vertices is less than or equal to the average length of all the n+1 minimum spanning trees of the induced graph on n vertices is presented. The theorem generalizes the result for any graph without any constraints.

UR - https://www.scopus.com/pages/publications/0033591575

U2 - 10.1016/S0020-0190(99)00068-X

DO - 10.1016/S0020-0190(99)00068-X

M3 - Article

AN - SCOPUS:0033591575

SN - 0020-0190

VL - 70

SP - 241

EP - 243

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

On average edge length of minimum spanning trees

Abstract

Access to Document

Other files and links

Fingerprint

Cite this