Rooted binary
This content will become publicly available on February 1, 2025
 Award ID(s):
 2116322
 NSFPAR ID:
 10522038
 Publisher / Repository:
 Elsevier
 Date Published:
 Journal Name:
 Advances in Applied Mathematics
 Volume:
 153
 Issue:
 C
 ISSN:
 01968858
 Page Range / eLocation ID:
 102612
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract galled trees generalize rooted binary trees to allow a restricted class of cycles, known asgalls . We build upon the WedderburnEtherington enumeration of rooted binary unlabeled trees withn leaves to enumerate rooted binary unlabeled galled trees withn leaves, also enumerating rooted binary unlabeled galled trees withn leaves andg galls, . The enumerations rely on a recursive decomposition that considers subtrees descended from the nodes of a gall, adopting a restriction on galls that amounts to considering only the rooted binary$$0 \leqslant g \leqslant \lfloor \frac{n1}{2} \rfloor $$ $0\u2a7dg\u2a7d\lfloor \frac{n1}{2}\rfloor $normal unlabeled galled trees in our enumeration. We write an implicit expression for the generating function encoding the numbers of trees for alln . We show that the number of rooted binary unlabeled galled trees grows with , exceeding the growth$$0.0779(4.8230^n)n^{\frac{3}{2}}$$ $0.0779(4.{8230}^{n}){n}^{\frac{3}{2}}$ of the number of rooted binary unlabeled trees without galls. However, the growth of the number of galled trees with only one gall has the same exponential order 2.4833 as the number with no galls, exceeding it only in the subexponential term,$$0.3188(2.4833^n)n^{\frac{3}{2}}$$ $0.3188(2.{4833}^{n}){n}^{\frac{3}{2}}$ compared to$$0.3910n^{\frac{1}{2}}$$ $0.3910{n}^{\frac{1}{2}}$ . For a fixed number of leaves$$0.3188n^{\frac{3}{2}}$$ $0.3188{n}^{\frac{3}{2}}$n , the number of gallsg that produces the largest number of rooted binary unlabeled galled trees lies intermediate between the minimum of and the maximum of$$g=0$$ $g=0$ . We discuss implications in mathematical phylogenetics.$$g=\lfloor \frac{n1}{2} \rfloor $$ $g=\lfloor \frac{n1}{2}\rfloor $ 
Consider the Aldous Markov chain on the space of rooted binary trees with
n labeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix 1 ≤k <n and project the leaf mass onto the subtree spanned by the firstk leaves. This yields a binary tree with edge weights that we call a “decoratedk ‐tree with total massn .” We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decoratedk ‐trees evolve as Markov chains themselves, and are projectively consistent overk . The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is then →∞ continuum analog of the Aldous chain and will be taken up elsewhere. 
Jurdziński, T ; Schmid, S (Ed.)In the multiparty equality problem, each of the n nodes starts with a kbit input. If there is a mismatch between the inputs, then at least one node must be able to detect it. The cost of a multiparty equality protocol is the total number of bits sent in the protocol. We consider the problem of minimizing this communication cost under the local broadcast model for the case where the underlying communication graph is undirected. In the local broadcast model of communication, a message sent by a node is received identically by all of its neighbors. This is in contrast to the classical pointtopoint communication model, where a message sent by a node to one of its neighbors is received only by its intended recipient. Under pointtopoint communication, there exists a simple protocol which is competitive within a factor 2 of the lower bound [1]. In this protocol, a rooted spanning tree is fixed and each node sends its entire input to its parent in the tree. On receiving a value from its child, a node compares it against its own input to check if the two values match. Ignoring lower order additive terms, a more complicated protocol comes within a factor 4/3 of the lower bound and is tight for certain classes of graphs [1]. Tight results, ignoring lower order terms, are also known for complete graphs [2, 9]. We study the multiparty equality problem under the local broadcast model. Recently, our work has shown that the connectivity requirements for Byzantine consensus are lower in the local broadcast model as compared to the classical model [7, 8]. In this work, 1. we identify a lower bound for the multiparty equality problem in this model. 2. we first identify simple protocols, wherein nodes are restricted to either transmit their entire input or not transmit anything at all, and find that these can cost Ω(logn) times the lower bound using existing example for the set cover problem [12]. 3. we then design a protocol to solve the problem within a constant factor of the lower bound.more » « less

Phylogenetic network is an evolutionary model that uses a rooted directed acyclic graph (instead of a tree) to model an evolutionary history of species in which reticulate events (e.g., hybrid speciation or horizontal gene transfer) occurred. Treechild network is a kind of phylogenetic network with structural constraints. Existing approaches for treechild network reconstruction can be slow for large data. In this paper, we present several computational approaches for bounding from below the number of reticulations in a treechild network that displays a given set of rooted binary phylogenetic trees. Through simulation, we demonstrate that the new lower bounds on the reticulation number for treechild networks can practically be computed for large tree data. The bounds can provide estimates of reticulation for relatively large data.more » « less

Waves of misery is a phenomenon where spikes of many node splits occur over short periods of time in tree indexes. Waves of misery negatively affect the performance of tree indexes in insertionheavy workloads. Waves of misery have been first observed in the context of the Btree, where these waves cause unpredictable index performance. In particular, the performance of search and indexupdate operations deteriorate when a wave of misery takes place, but is more predictable between the waves. This paper investigates the presence or lack of waves of misery in several Rtree variants, and studies the extent of which these waves impact the performance of each variant. Interestingly, although having poorer query performance, the Linear and Quadratic Rtrees are found to be more resilient to waves of misery than both the Hilbert and R*trees. This paper presents several techniques to reduce the impact in performance of the waves of misery for the Hilbert and R*trees. One way to eliminate waves of misery is to force node splits to take place at regular times before nodes become full to achieve deterministic performance. The other way is that upon splitting a node, do not split it evenly but rather at different node utilization factors. This allows leaf nodes not to fill at the same pace. We study the impact of two new techniques to mitigate waves of misery after the tree index has been constructed, namely Regular Elective Splits (RES, for short) and Unequal Random Splits (URS, for short). Our experimental investigation highlights the tradeoffs in performance of the introduced techniques and the pros and cons of each technique.