Identifying phylogenetic trees

A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X. Such a tree is called an X-tree and, for a collection of partitions of subsets of X, characterisations for the existence and uniqueness of an X-tree that displays have been previously given in terms of chordal graphs. In this paper, we obtain two closely related characterisations also in terms of chordal graphs. The first describes when identifies an X-tree, and the second describes when a compatible subset of is of maximum size.     

最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].     

The Two-Point Codes with the Designed Distance on a Hermitian Curve in Even Characteristic

In Homma M and Kim SJ [2], the authors considered two-point codes on a Hermitian curve defined over fields of odd characteristic. In this paper, we study the geometry of a Hermitian curve over fields of even characteristic and classify the two-point codes whose minimum distances agree with the designed ones.     

An Improved Extra-Gradient Method for Minimizing a Sum of p-norms—A Variational Inequality Approach

This paper presents a variational inequality (VI) approach to the problem of minimizing a sum of p-norms. First the original problem is reformulated as an equivalent linear VI. Then an improved extra-gradient method is presented to solve the linear VI. Applications to the problem of p-norm Steiner Minimum Trees (SMT) shows that the proposed method is effective. Comparison with the general extra-gradient method is also provided to show the improvements of the new method.     

STRONG LAW OF LARGE NUMBERS AND ASYMPTOTIC EQUIPARTITION PROPERTY FOR NONSYMMETRIC MARKOV CHAIN FIELDS ON CAYLEY TREES

Some strong laws of large numbers for the frequcncies of occurrence of states and ordered couples of states for nonsymmetric Markov chain fields(NSMC)on Cayley trees are studied.In the proof,a new technique for the study of strong liinit theorems of Markov chains is extended to the case of Markov chain fields.The asymptotic equiparti- tion properties with almost everywhere(a.e.)convergence for NSMC on Cayley trees are obtained.     

LIMITING BEHAVIOR OF UNIFORM RECURSIVE TREES

The authors consider the limiting behavior of various branches in a uniform recursive tree with size growing to infinity.The limiting distribution ofζ_(n,m),the number of branches with size m in a uniform recursive tree of order n,converges weakly to a Poisson distribution with parameter 1/m with convergence of all moments.The size of any large branch tends to infinity almost surely.     

Quadratically constrained minimum cross-entropy analysis

Quadratically constrained minimum cross-entropy problem has recently been studied by Zhang and Brockett through an elaborately constructed dual. In this paper, we take a geometric programming approach to analyze this problem. Unlike Zhang and Brockett, we separate the probability constraint from general quadratic constraints and use two simple geometric inequalities to derive its dual problem. Furthermore, by using the dual perturbation method, we directly prove the strong duality theorem and derive a dual-to-primal conversion formula. As a by-product, the perturbation proof gives us insights to develop a computation procedure that avoids dual non-differentiability and allows us to use a general purpose optimizer to find an-optimal solution for the quadratically constrained minimum cross-entropy analysis.     

Tree-gel and loop-gel conversions in nonlinear polymerization

Ａｓｉｓｗｅｌｌｋｎｏｗｎ,ｔｈｅｔｈｅｏｒｙｆｏｒｎｏｎｌｉｎｅａｒｐｏｌｙｍｅｒｉｚａｔｉｏｎｓｗａｓｉｎｉｔｉａｔｅｄｂｙＦｌｏｒｙａｎｄＳｔｏｃｋｍａｙｅｒ[1—3].ＭｉｌｌｅｒａｎｄＭａｃｏｓｋｏ[4—6]ｐｒｏｐｏｓｅｄａｒｅｃｕｒｓｉｖｅｍｅｔｈｏｄｆｏｒｄｅａｌｉｎｇｗｉｔｈｔｈｅｐｒｏｂｌｅｍｏｆｔｈｅｐｏｓｔｇｅｌｐｒｏｐｅｒｔｉｅｓｏｆｔｈｅｎｅｔｗｏｒｋｆｏｒｍｉｎｇｐｏｌｙｍｅｒｉｚａｔｉｏｎ.Ｓｔｅｐｔｏ[7]ｉｎｖｅｓｔｉｇａｔｅｄｔｈｅｇｅｌｇｅｌｒｅａｃｔｉｏｎｏｆＲＡｆｔ…     

Equilibrium polymerization in a solvent: Solution on the Bethe lattice

The lattice model for equilibrium polymerization in a solvent proposed by Wheeler and Pfeuty is solved exactly on a Bethe lattice (core of a Caylay tree) with general coordination numberq. Earlier mean-field results are reobtained in the limitq, but the phase diagrams show deviations from them for finiteq. Whenq=2, our results turn into the solution of the one-dimensional problem. Although the model is solved directly, without the use of the correspondence between the equilibrium polymerization model and the diluten0 model, we verified that the latter model may also be solved on the Bethe lattice, its solution being identical to the direct solution in all parameter space. As observed in earlier studies of the puren0 vector model, the free energy is not always convex. We obtain the region of negative susceptibility for our solution and compare this result with mean field and renormalization group (-expansion) calculations.