Premium
Realization of a symmetric terminal capacity matrix by a tree with the minimum diameter
Author(s) -
Ozawa T.
Publication year - 1980
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230100204
Subject(s) - realization (probability) , terminal (telecommunication) , tree (set theory) , mathematics , combinatorics , matrix (chemical analysis) , star (game theory) , upper and lower bounds , topology (electrical circuits) , algorithm , discrete mathematics , computer science , mathematical analysis , materials science , telecommunications , statistics , composite material
Trees realizing a terminal capacity matrix (TCM) have a unique layer structure. An algorithm making use of this layer structure is presented for construction of a tree which realizes the TCM with the smallest possible diameter. This minimum‐diameter tree has layers of stars. An upper bound on the minimum diameter is given for a prescribed number of vertices. Also presented are algorithms to construct a star and a tree of diameter 3 which realize the TCM as a minimum requirement matrix.