✦ LIBER ✦

Balance vertices in trees

✍ Scribed by Reid, K. B.

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 100 KB
Volume: 34
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199912)34:4<264::aid-net5>3.0.co;2-a

No coin nor oath required. For personal study only.

✦ Synopsis

A new notion of balanced bipartitions of the vertices in a tree T is introduced and studied. It gives rise to a new central set of vertices in T, each of which can be considered to be a discrete version of the center of gravity of T. We seek vertices x, called balance vertices, such that the two sums of the distances from x to all the vertices in each of two subtrees of T are as equal as possible, where the two subtrees have only x in common, but, together, contain all the vertices of T. We discuss some of the computation involved in a first step in determining the balance vertices. We prove that the median vertices, the center vertices, and the balance vertices may be arbitrarily far apart. We also prove that the set of balance vertices of a tree T consists of a single vertex or two adjacent vertices; the proof involves a new type of "double orientation" of the edges of T.

📜 SIMILAR VOLUMES

Vertices of degree k in random unlabeled

Vertices of degree k in random unlabeled trees

✍ Konstantinos Panagiotou; Makrand Sinha 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 1 views

Let H n be the class of unlabeled trees with n vertices, and denote by H n a tree that is drawn uniformly at random from this set. The asymptotic behavior of the random variable deg k (H n ) that counts vertices of degree k in H n was studied, among others, by Drmota and Gittenberger in [J Graph The

General Balanced Trees

✍ Arne Andersson 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 117 KB

We show that, in order to achieve efficient maintenance of a balanced binary search tree, no shape restriction other than a logarithmic height is required. The obtained class of trees, general balanced trees, may be maintained at a logarithmic amortized cost with no balance information stored in the

AVL Trees with Relaxed Balance

✍ Kim S. Larsen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 185 KB

The idea of relaxed balance is to uncouple the rebalancing in search trees from the updating in order to speed up request processing in main-memory databases. In this paper, we describe a relaxed version of AVL trees. We prove that each update gives rise to at most a logarithmic number of rebalancin

Balancing two spanning trees

✍ Matthias Kriesell 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

Interpolation theorem for the number of

Interpolation theorem for the number of end-vertices of spanning trees

✍ Seymour Schuster 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract The following interpolation theorem is proved: If a graph __G__ contains spanning trees having exactly __m__ and __n__ end‐vertices, with __m__ < __n__, then for every integer __k, m < k < n, G__ contains a spanning tree having exactly __k__ end‐vertices. This settles a problem posed by

Vertices contained in every minimum domi

Vertices contained in every minimum dominating set of a tree

✍ Mynhardt, C. M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB

In this article we begin the study of the vertex subsets of a graph G which consist of the vertices contained in all, or in no, respectively, minimum dominating sets of G. We characterize these sets for trees, and also obtain results on the vertices contained in all minimum independent dominating se