On the covariance of the level sizes in random recursive trees

In this paper we study the covariance structure of the number of nodes k and l steps away from the root in random recursive trees. We give an analytic expression valid for all k, l and tree sizes N. The fraction of nodes k steps away from the root is a random probability distribution in k. The expression for the covariances allows us to show that the total variation distance between this (random) probability distribution and its mean converges in probability to zero. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 519–539, 2002     

Rigidity of Branch Groups Acting on Rooted Trees

Automorphisms of groups acting faithfully on rooted trees are studied. We find conditions under which every automorphism of such a group is induced by a conjugation from the full automorphism group of the rooted tree. These results are applied to known examples such as Grigorchuk groups, Gupta–Sidki group, etc.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Extension of multivariate regression trees to interval data. Application to electricity load profiling

Summary  Several data can be presented as interval curves where intervals reflect a within variability. In particular, this representation is well adapted for load profiles, which depict the electricity consumption of a class of customers. Electricity load profiling consists in assigning a daily load curve to a customer based on their characteristics such as energy requirement. Within the load profiling scope, this paper investigates the extension of multivariate regression trees to the case of interval dependent (or response) variables. The tree method aims at setting up simultaneously load profiles and their assignment rules based on independent variables. The extension of multivariate regression trees to interval responses is detailed and a global approach is defined. It consists in a first stage of a dimension reduction of the interval response variables. Thereafter, the extension of the tree method is applied to the first principal interval components. Outputs are the classes of the interval curves where each class is characterized both by an interval load profile (e.g. the class prototype) and an assignment rule based on the independent variables.     

Establishment of hybrid-derived offspring populations in the Ohomopterus ground beetles through unidirectional hybridization

An approach to deduce the mechanism of stabilization of the hybrid-derived populations in the Ohomopterus ground beetles has been made by comparative studies on the phylogenetic trees of the mitochondrial and nuclear DNA. A phylogenetic tree based on the internal transcribed spacer (ITS) of nuclear ribosomal gene roughly reflects the relations of morphological species group, while mitochondrial NADH dehydrogenase subunit 5 (ND5) gene shows a considerable different topology on the tree; there exist several geographically-linked lineages, most of which consist of more than one species. These results suggest that the replacement of mitochondria has occurred widely in the Ohomopterus species. In most cases, hybridization is unidirectional, i.e., the species A (♂) hybridized with another species B (♀) and not vice versa, with accompanied replacement of mitochondria of A by those of B. The results also suggest that partial or complete occupation of the distribution territory by a hybrid-derived morphological species. The morphological appearance of the resultant hybrid-derivatives are recognized as that of the original species A. Emergence of a morphological new species from a hybrid-derived population has been exemplified.     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

Note on the application of the reduced graph model in conjunction with search trees to the enumeration ofKekulé structures

The reduced graph model, when used in conjunction with the search trees method, provides a novel combinatorial procedure for the enumeration and generation ofKekulé structures. The procedure is suited for large benzenoid hydrocarbons consisting of cata- and thin peri-condensed parts.

---

Zur Anwendung des Reduced Graph Model im Zusammenhang mit Search Trees zur Ermittlung der Anzahl möglicherKekulé-Strukturen

Zusammenfassung Das Modell erlaubt mit der im Titel genannten Kombination eine neuartige Methode zur Ermittlung und Generierung vonKekulé-Strukturen. Das Verfahren ist für große benzoide Kohlenwasserstoffe geeignet, die aus cata- und (dünnen) peri-kondensierten Teilstrukturen bestehen.

     

A greedy algorithm for finding maximum spanning trees in infinite graphs

In finite graphs, greedy algorithms are used to find minimum spanning trees (MinST) and maximum spanning trees (MaxST). In infinite graphs, we illustrate a general class of problems where a greedy approach discovers a MaxST while a MinST may be unreachable. Our algorithm is a natural extension of Prim's to infinite graphs with summable and strictly positive edge weights, producing a sequence of finite trees that converge to a MaxST.