The average height of r-typly rooted planted plane trees

In this paper we generalize a result of de Bruijn, Knuth und Rice concerning the average height of planted plane trees withn nodes. First we compute the number of allr-typly rooted planted plane trees (r-trees) withn nodes and height less than or equal tok. Assuming that all planted plane trees withn nodes are equally likely, we show, that in the average a planted plane tree is a 3-tree for largen; for this distribution we compute also the cumulative distribution function and the variance. Finally, we shall derive an exact expression and its asymptotic equivalent for the average height \(\bar h_r \) (n) of anr-tree withn nodes. We obtain for all ε>0 $$\bar h_r (n) = \sqrt {\pi n} - \frac{1}{2}(r - 2) + O(1n(n)/n^{1/2 - \varepsilon } ).$$      

A metric for rooted trees with unlabeled vertices based on nested parentheses

In this paper, we propose a new metric for rooted trees with unlabeled vertices based on alignments of nested parenthesis strings. We prove that the time complexity for computing this metric is NP-hard and present a 1.5-approximation algorithm for it.     

A note on fibered projective plane geometry

In this work, we consider the role of the triangular norm in the theory of fibered projective planes as introduced in Kuijken and Van Maldeghem [L. Kuijken, H. Van Maldeghem, Fibered geometries, Discrete Mathematics 255 (2002) 259-274]. As a way of example, we consider fibered harmonic conjugates and a fibered version of Reidemeister’s condition.     

Complexity analysis of balloon drawing for rooted trees

In a balloon drawing of a tree, all the children under the same parent are placed on the circumference of the circle centered at their parent, and the radius of the circle centered at each node along any path from the root reflects the number of descendants associated with the node. Among various styles of tree drawings reported in the literature, the balloon drawing enjoys a desirable feature of displaying tree structures in a rather balanced fashion. For each internal node in a balloon drawing, the ray from the node to each of its children divides the wedge accommodating the subtree rooted at the child into two sub-wedges. Depending on whether the two sub-wedge angles are required to be identical or not, a balloon drawing can further be divided into two types: even sub-wedge and uneven sub-wedge types. In the most general case, for any internal node in the tree there are two dimensions of freedom that affect the quality of a balloon drawing: (1) altering the order in which the children of the node appear in the drawing, and (2) for the subtree rooted at each child of the node, flipping the two sub-wedges of the subtree. In this paper, we give a comprehensive complexity analysis for optimizing balloon drawings of rooted trees with respect to angular resolution, aspect ratio and standard deviation of angles under various drawing cases depending on whether the tree is of even or uneven sub-wedge type and whether (1) and (2) above are allowed. It turns out that some are NP-complete while others can be solved in polynomial time. We also derive approximation algorithms for those that are intractable in general.     

A note on 2-facial coloring of plane graphs

An l-facial coloring of a plane graph is a vertex coloring such that any two different vertices joined by a facial walk of length at most l receive distinct colors. It is known that every plane graph admits a 2-facial coloring using 8 colors [D. Král, T. Madaras, R. Škrekovski, Cyclic, diagonal and facial coloring, European J. Combin. 3-4 (26) (2005) 473-490]. We improve this bound for plane graphs with large girth and prove that if G is a plane graph with girth g?14 (resp. 10, 8) then G admits a 2-facial coloring using 5 colors (resp. 6, 7). Moreover, we give exact bounds for outerplanar graphs and K₄-minor free graphs.     

A note on total ordering multicast using propagation trees

Jia (1995) proposed a multicast scheme, using propagation trees, to ensure the total ordering (including causal ordering) delivery of messages for group communication. Our study indicates that causal relation between some messages may not actually be presented in this protocol. We then present a revised approach for closed group communication     

A note on minimal d-separation trees for structural learning

Structural learning of a Bayesian network is often decomposed into problems related to its subgraphs, although many approaches without decomposition were proposed. In 2006, Xie, Geng and Zhao proposed using a d-separation tree to improve the power of conditional independence tests and the efficiency of structural learning. In our research note, we study a minimal d-separation tree under a partial ordering, by which the maximal efficiency can be obtained. Our results demonstrate that a minimal d-separation tree of a directed acyclic graph (DAG) can be constructed by searching for the clique tree of a minimal triangulation of the moral graph for the DAG.     

Efficient generation of plane trees

A rooted plane tree is a rooted tree with a left-to-right ordering specified for the children of each vertex. In this paper we give a simple algorithm to generate all rooted plane trees with at most n vertices. The algorithm uses O(n) space and generates such trees in O(1) time per tree without duplications. The algorithm does not output entire trees but the difference from the previous tree. By modifying the algorithm we can generate without duplications all rooted plane trees having exactly n vertices in O(1) time per tree, all rooted plane trees having at most n vertices with maximum degree at most D in O(1) time per tree, and all rooted plane trees having exactly n vertices including exactly c leaves in O(n−c) time per tree. Also we can generate without duplications all (non-rooted) plane trees having exactly n vertices in O(n³) time per tree.     

A fixed-parameter tractability result for multicommodity demand flow in trees

We study an NP-hard (and MaxSNP-hard) problem in trees—Multicommodity Demand Flow—dealing with demand flows between pairs of nodes and trying to maximize the value of the routed flows. This problem has been intensively studied for trees as well as for general graphs mainly from the viewpoint of polynomial-time approximation algorithms. By way of contrast, we provide an exact dynamic programming algorithm for this problem that works well whenever some natural problem parameter is small, a reasonable assumption in several applications. More specifically, we prove fixed-parameter tractability with respect to the maximum number of the input flows at any tree node.     

A note on an optimal result on fault-tolerant cycle-embedding in alternating group graphs

In a recently published paper [Z.-J. Xue, S.-Y. Liu, An optimal result on fault-tolerant cycle-embedding in alternating group graphs, Inform. Process. Lett. 109 (21-22) (2009) 1197-1201], the authors showed that for a set of faulty vertices F in an n-dimensional alternating group graph AGn, AGn−F remains pancyclic if |F|≤2n−6. However, the proof of the result is flawed. We will prove the theorem again correcting the defects in the previous proof.     

A note on proper affine vector fields in non-static plane symmetric space-times

Themost general form of non-static plane symmetric space-times is considered to study proper affine vector fields by using holonomy and decomposability, the rank of the 6 × 6 Riemannmatrix and direct integration techniques. Studying proper affine vector fields in each nonstatic case of the above space-times it is shown that very special classes of the above space-times admit proper affine vector fields. We also discuss the Lie algebra in each case.     

A note on the controllability for the wave equation in nonsmooth plane domains

We study exact boundary controllability for a two-dimensional wave equation in a region which is an angular sector of a circle or an angular sector of an annular region. The control, of Neumann type, acts on the curved part of the boundary, while in the straight part we impose homogeneous Dirichlet boundary condition. The initial state has finite energy and the control is square integrable.