On average edge length of minimum spanning trees

被引：0
|
作者：
Nath, SK [1 ]
Chowdhury, RA [1 ]
Kaykobad, M [1 ]
机构：
[1] Bangladesh Univ Engn & Technol, Dept Comp Sci & Engn, Dhaka 1000, Bangladesh
来源：
INFORMATION PROCESSING LETTERS | 1999年 / 70卷 / 05期
关键词：
minimum spanning tree; complete graph; average edge length;
D O I：
10.1016/S0020-0190(99)00068-X
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
This paper presents a theorem that asserts that average edge length of the minimum spanning tree of a complete graph on n + 1 vertices is less than or equal to the average edge length of all the n + 1 minimum spanning trees of the induced graph on n vertices. The result is also in compliance with results given by Frieze and Steele. (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：241 / 243
页数：3
相关论文
共 50 条
  • [1] On minimum edge ranking spanning trees
    Makino, K
    Uno, Y
    Ibaraki, T
    JOURNAL OF ALGORITHMS, 2001, 38 (02) : 411 - 437
  • [2] Average distance, minimum degree, and spanning trees
    Dankelmann, P
    Entringer, R
    JOURNAL OF GRAPH THEORY, 2000, 33 (01) : 1 - 13
  • [3] ON RANDOM MINIMUM LENGTH SPANNING-TREES
    FRIEZE, AM
    MCDIARMID, CJH
    COMBINATORICA, 1989, 9 (04) : 363 - 374
  • [4] On Minimum Average Stretch Spanning Trees in Polygonal 2-Trees
    Narayanaswamy, N. S.
    Ramakrishna, G.
    ALGORITHMS AND COMPUTATION, WALCOM 2014, 2014, 8344 : 310 - 321
  • [5] On minimum average stretch spanning trees in polygonal 2-trees
    Narayanaswamy, N. S.
    Ramakrishna, G.
    THEORETICAL COMPUTER SCIENCE, 2015, 575 : 56 - 70
  • [6] Minimum spanning trees in networks with varying edge weights
    Kevin R. Hutson
    Douglas R. Shier
    Annals of Operations Research, 2006, 146 : 3 - 18
  • [7] Minimum edge ranking spanning trees of split graphs
    Makino, Kazuhisa
    Uno, Yushi
    Ibaraki, Toshihide
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (16) : 2373 - 2386
  • [8] Minimum spanning trees in networks with varying edge weights
    Hutson, Kevin R.
    Shier, Douglas R.
    ANNALS OF OPERATIONS RESEARCH, 2006, 146 (1) : 3 - 18
  • [9] Minimum edge ranking spanning trees of threshold graphs
    Makino, K
    Uno, Y
    Ibaraki, T
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2002, 2518 : 428 - 440
  • [10] Random minimum length spanning trees in regular graphs
    Beveridge, A
    Frieze, A
    McDiarmid, C
    COMBINATORICA, 1998, 18 (03) : 311 - 333
12345