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 modular inequalities in variable L p spaces

We show that the Hardy-Littlewood maximal operator and a class of Calderón-Zygmund singular integrals satisfy the strong type modular inequality in variable L^p spaces if and only if the variable exponent p(x) ∼ const. Received: 15 September 2004     

A finiteness result for Heegaard splittings

In this paper we show that for a given 3-manifold and a given Heegaard splitting there are finitely many preferred decomposing systems of 3g−3 disjoint essential disks. These are characterized by a combinatorial criterion which is a slight strengthening of Casson-Gordon's rectangle condition. This is in contrast to fact that in general there can exist infinitely many such systems of disks which satisfy just the Casson-Gordon rectangle condition.     

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.     

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.     

Exponential decay of eigenfunctions in many-body type scattering with second-order perturbations

We show the exponential decay of eigenfunctions of second-order geometric many-body type Hamiltonians at non-threshold energies. Moreover, in the case of first-order and small second-order perturbations we show that there are no eigenfunctions with positive energy.     

Study of the dynamic structure factor of strong glasses

The dynamic structure factors (DSFs) of several strong glasses (SF6, SF10, BK7, SUPRASIL) measured by Brillouin light scattering spectroscopy are reported. Spectra have been collected, at and above room temperature, at two scattering angles, θ=90° and θ=180° corresponding to exchanged wavevector q values ranging from 0.0256 to 0.0448 nm⁻¹. In particular we find that the isotropic spectral lineshapes are in all cases well described by the simple hydrodynamic theory of an amorphous solid. The width of the Brillouin peaks are found to be consistent with the predicted q² dependence at both investigated temperatures. This damping is however found to account only partially for the strong asymmetry of the Brillouin line clearly visible on a logarithmic intensity scale. As a matter of fact there is an excess intensity in the very low frequency plateau underlying the central component. The height of this plateau and hence the entire lineshape is well reproduced if a relaxation process is taken into account in the hydrodynamic equations. Owing to the intense elastic scattering we are able to determine unambiguously only the ratio between amplitude and characteristic time of this process which quantifies the sound dispersion to be of the order of a few percent in all samples. The temperature dependence of the parameters indicates that this relaxation cannot be attributed to thermally activated relaxation phenomena. These general findings favorably compare with molecular dynamics simulation results on similar systems.     

Stability results for Mountain Pass and Linking type solutions of semilinear problems involving Dirichlet forms

Some stability results for Mountain Pass and Linking type solutions of semilinear problems involving a very general class of Dirichlet forms are stated. The non linear terms are supposed to have a suitable superlinear growth and the family of Dirichlet forms is required to be dominated from below and from above by a fixed diffusion type form. Some concrete examples are also given.