Bandwidths and profiles of trees
type: Item
instance of: scholarly article
title: Bandwidths and profiles of trees
zbMATH Open document ID: 0588.05015
DOI: 10.1016/0095-8956(87)90052-9
author: Andrew Odlyzko
author: Herbert S. Wilf
published in: Journal of Combinatorial Theory. Series B
publication date: 1987-01-01T00:00:00Z
review text: The bandwidths of labelled, rooted trees are studied. It is shown that the average bandwidth of trees of n vertices is \(>C_ 1\sqrt{n}\) and \(<C_ 2\sqrt{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. [See also P. Kirschenhofer's review of the authors' conference article with the same title published in Graph theory with applications to algorithms and computer science, Proc. 5th Int. Conf., Kalamazoo/Mich. 1984, 605-622 (1985; Zbl 0575.05023).]
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 3943838
zbMATH Keywords: bandwidth
zbMATH Keywords: width
zbMATH Keywords: tree
zbMATH Keywords: NP-complete
zbMATH Keywords: Perron-Frobenius
MaRDI profile type: Publication
full work available at URL: 0095-8956(87)90052-9
OpenAlex ID: W1995937439
cites work: A remark on a problem of Harary
cites work: The average height of binary trees and other simple trees
cites work: Q3254327
cites work: Complexity Results for Bandwidth Minimization
cites work: On the Altitude of Nodes in Random Trees
cites work: Q5616724
cites work: The NP-completeness of the bandwidth minimization problem
cites work: On the height of trees
cites work: Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
cites work: On the Distribution of the Number of Vertices in Strata of a Random Tree
cites work: Q3290777
description: scientific article; zbMATH DE number 3943838