On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance

The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees.Received March 16, 2004     

Admissible slopes for monotone and convex interpolation

Summary In many applications, interpolation of experimental data exhibiting some geometric property such as nonnegativity, monotonicity or convexity is unacceptable unless the interpolant reflects these characteristics. This paper identifies admissible slopes at data points of variousC ¹ interpolants which ensure a desirable shape. We discuss this question, in turn for the following function classes commonly used for shape preserving interpolations: monotone polynomials,C ¹ monotone piecewise polynomials, convex polynomials, parametric cubic curves and rational functions.     

On the electron energy spectrum in heavily doped non-parabolic semiconductors

An attempt is made to present a simple theoretical analysis of the energy-wave vector dispersion relation of the conduction electrons in heavily doped non-parabolic semiconductors forming band tails. We observe that the complex energy spectrum in doped small-gap materials whose unperturbed conduction band is described by the three band model of Kane is due to the interaction of the impurity atoms in the tail with the spin-orbit splitting constant of the valence band (Δ), For band-gap (E_g)<Δ the imaginary part predominates which tails in to the conduction band. For the opposite inequality the real part comes in to play which tails in to the split-off band. In the absence of the band tailing effect, the imaginary part of the complex energy spectrum vanishes and the same is also true for doped two-band Kane-type and parabolic energy bands respectively. The present formulation helps us in investigating the Boltzmann transport equation dependent transport properties of degenerate semiconductors and are expected to agree better with experiments. The well-known results of unperturbed three and two band models of Kane together with wide-gap parabolic energy bands have been obtained as special cases of our generalized analysis under certain limiting conditions.     

Normalization of complex-valued planar vector fields which degenerate along a real curve

Taking as a start point the recent article of Meziani [7], we present several results concerning the normalization of a class of complex vector fields in the plane which degenerate along a real curve. We mainly deal with operators with finite regularity and analyze both the local situation as well as the case of normalization near a circle. Some related questions (e.g., on semi-global solvability and on the normalization of a class of generalized Mizohata operators) are also discussed.     

Rank estimation in reduced-rank regression

Reduced rank regression assumes that the coefficient matrix in a multivariate regression model is not of full rank. The unknown rank is traditionally estimated under the assumption of normal responses. We derive an asymptotic test for the rank that only requires the response vector have finite second moments. The test is extended to the nonconstant covariance case. Linear combinations of the components of the predictor vector that are estimated to be significant for modelling the responses are obtained.     

From a Nonlinear, Nonconvex Variational Problem to a Linear, Convex Formulation

   Abstract. We propose a general approach to deal with nonlinear, nonconvex variational problems based on a reformulation of the problem resulting in an optimization problem with linear cost functional and convex constraints. As a first step we explicitly explore these ideas to some one-dimensional variational problems and obtain specific conclusions of an analytical and numerical nature.     

Rank one perturbations at infinite coupling in Pontryagin spaces

In this paper we relate the operators in the operator representations of a generalized Nevanlinna function N(z) and of the function −N(z)⁻¹ under the assumption that z=∞ is the only (generalized) pole of nonpositive type. The results are applied to the Q-function for S and H and the Q-function for S and H^∞, where H is a self-adjoint operator in a Pontryagin space with a cyclic element w, H^∞ is the self-adjoint relation obtained from H and w via a rank one perturbation at infinite coupling, and S is the symmetric operator given by S=H∩H^∞.     

Attractors for 2D-Navier-Stokes models with delays

The existence of an attractor for a 2D-Navier-Stokes system with delay is proved. The theory of pullback attractors is successfully applied to obtain the results since the abstract functional framework considered turns out to be nonautonomous. However, on some occasions, the attractors may attract not only in the pullback sense but in the forward one as well. Also, this formulation allows to treat, in a unified way, terms containing various classes of delay features (constant, variable, distributed delays, etc.). As a consequence, some results for the autonomous model are deduced as particular cases of our general formulation.     

Controlling rough paths

We formulate indefinite integration with respect to an irregular function as an algebraic problem which has a unique solution under some analytic constraints. This allows us to define a good notion of integral with respect to irregular paths with Hölder exponent greater than 1/3 (e.g. samples of Brownian motion) and study the problem of the existence, uniqueness and continuity of solution of differential equations driven by such paths. We recover Young's theory of integration and the main results of Lyons’ theory of rough paths in Hölder topology.