Bandwidths and profiles of trees

Andrew M. Odlyzko; Herbert S. Wilf

doi:10.1016/0095-8956(87)90052-9

Bandwidths and profiles of trees

Andrew M. Odlyzko
, Herbert S. Wilf

School of Mathematics

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

15 Scopus citations

Abstract

The bandwidths of labeled, rooted trees are studied. It is shown that the average bandwidth of trees of n vertices is >C₁ n and <C₂ n log n. The width of such a tree is the largest number of vertices at a constant distance from the root. The distribution of the width and its relationship with the bandwidth are studied. Results include generating functions for trees by width, and asymptotic estimates.

Original language	English (US)
Pages (from-to)	348-370
Number of pages	23
Journal	Journal of Combinatorial Theory, Series B
Volume	42
Issue number	3
DOIs	https://doi.org/10.1016/0095-8956(87)90052-9
State	Published - Jun 1987

Publisher link

10.1016/0095-8956(87)90052-9

Find It

Find It at U of M Libraries

Cite this

@article{e8988dea68e3443b898df66b74b6696c,

title = "Bandwidths and profiles of trees",

abstract = "The bandwidths of labeled, rooted trees are studied. It is shown that the average bandwidth of trees of n vertices is >C1 n and 2 n log n. The width of such a tree is the largest number of vertices at a constant distance from the root. The distribution of the width and its relationship with the bandwidth are studied. Results include generating functions for trees by width, and asymptotic estimates.",

author = "Odlyzko, \{Andrew M.\} and Wilf, \{Herbert S.\}",

year = "1987",

month = jun,

doi = "10.1016/0095-8956(87)90052-9",

language = "English (US)",

volume = "42",

pages = "348--370",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Bandwidths and profiles of trees

AU - Odlyzko, Andrew M.

AU - Wilf, Herbert S.

PY - 1987/6

Y1 - 1987/6

N2 - The bandwidths of labeled, rooted trees are studied. It is shown that the average bandwidth of trees of n vertices is >C1 n and 2 n log n. The width of such a tree is the largest number of vertices at a constant distance from the root. The distribution of the width and its relationship with the bandwidth are studied. Results include generating functions for trees by width, and asymptotic estimates.

AB - The bandwidths of labeled, rooted trees are studied. It is shown that the average bandwidth of trees of n vertices is >C1 n and 2 n log n. The width of such a tree is the largest number of vertices at a constant distance from the root. The distribution of the width and its relationship with the bandwidth are studied. Results include generating functions for trees by width, and asymptotic estimates.

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

UR - https://www.scopus.com/pages/publications/38249035004#tab=citedBy

U2 - 10.1016/0095-8956(87)90052-9

DO - 10.1016/0095-8956(87)90052-9

M3 - Article

AN - SCOPUS:38249035004

SN - 0095-8956

VL - 42

SP - 348

EP - 370

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 3

ER -

Bandwidths and profiles of trees

Abstract

Publisher link

Find It

Other files and links

Fingerprint

Cite this