An analytic approach for the analysis of rotations in fringe-balanced binary search trees

This paper presents an analytic approach to the construction cost of fringe-balanced binary search trees. In [7], Mahmoud used a bottom-up approach and an urn model of Pólya. The present method is top-down and uses differential equations and Hwang's quasi-power theorem to derive the asymptotic normality of the number of rotations needed to construct such afringe balanced search tree. We also obtain the exact expectation and variance with this method. Although Pólya's urn model is no longer needed, we also present an elegant analysis of it based on an operator calculus as in [4].This research was supported by the Austrian Research Society (FWF) under the project number P12599-MAT.     

Optimization of lantadenes isolation and preparation of 22 β-hydroxyoleanonic acid

The lantadenes fraction from Lantana camara was isolated and transformed to the medicinally important intermediate 22β-hydroxyoleanonic acid. The compound was studied for hepatotoxicity using lantadene A as standard and found to be nontoxic. Published in Khimiya Prirodnykh Soedinenii, No. 4, pp. 357–358, July–August, 2006.     

About the Linear Stability of the Spherically Symmetric Solution for the Equations of a Barotropic Viscous Fluid under the Influence of Self-Gravitation

This paper is concerned with the question of linear stability of motionless, spherically symmetric equilibrium states of viscous, barotropic, self-gravitating fluids. We prove the linear asymptotic stability of such equilibria with respect to perturbations which leave the angular momentum, momentum, mass and the position of the center of gravity unchanged. We also give some decay estimates for such perturbations, which we derive from resolvent estimates by means of analytic semigroup theory.     

The three space problem in topological groups

We study compact, countably compact, pseudocompact, and functionally bounded sets in extensions of topological groups. A property P is said to be a three space property if, for every topological group G and a closed invariant subgroup N of G, the fact that both groups N and G/N have P implies that G also has P. It is shown that if all compact (countably compact) subsets of the groups N and G/N are metrizable, then G has the same property. However, the result cannot be extended to pseudocompact subsets, a counterexample exists under p=c. Another example shows that extensions of groups do not preserve the classes of realcompact, Dieudonné complete and μ-spaces: one can find a pseudocompact, non-compact Abelian topological group G and an infinite, closed, realcompact subgroup N of G such that G/N is compact and all functionally bounded subsets of N are finite. Several examples given in the article destroy a number of tempting conjectures about extensions of topological groups.     

The compound binomial risk model with time-correlated claims

In this paper, we consider the compound binomial risk model with the time-correlated claims. It is assumed that every main claim will produce a by-claim but the occurrence of the by-claim may be delayed. We obtain the recursive formula of the joint distribution of the surplus immediately prior to ruin and deficit at ruin. Furthermore, the ruin probability is given by means of ruin probability and the deficit at ruin of the classical compound binomial risk model. Finally, we derive an upper bound for the ruin probability.     

A large deviation principle for 2D stochastic Navier–Stokes equation

In this paper one specifies the ergodic behavior of the 2D-stochastic Navier–Stokes equation by giving a Large Deviation Principle for the occupation measure for large time. It describes the exact rate of exponential convergence. The considered random force is non-degenerate and compatible with the strong Feller property.     

Some geometrical aspects of semidefinite linear complementarity problems

This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R₀-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically.     

Eliminating graphs by means of parallel knock-out schemes

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.