Algorithms for clique-independent sets on subclasses of circular-arc graphs

A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a -free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n²). These algorithms suppose that an HCA model of the graph is given.     

A combinatorial algorithm for the TDMA message scheduling problem

In this paper, we introduce a combinatorial algorithm for the message scheduling problem on Time Division Multiple Access (TDMA) networks. In TDMA networks, time is divided in to slots in which messages are scheduled. The frame length is defined as the total number of slots required for all stations to broadcast without message collisions. The objective is to provide a broadcast schedule of minimum frame length which also provides the maximum throughput. This problem is known to be -hard, thus efficient heuristics are needed to provide solutions to real-world instances. We present a two-phase algorithm which exploits the combinatorial structure of the problem in order to provide high quality solutions. The first phase finds a feasible frame length in which the throughput is maximized in phase two. Computational results are provided and compared with other heuristics in the literature as well as to the optimal solutions found using a commercial integer programming solver. Experiments on 63 benchmark instances show that the proposed method is able to provide optimal frame lengths for all cases with near optimal throughput.     

Global error bounds for the extended vertical LCP

A new necessary and sufficient condition for the row -property is given. By using this new condition and a special row rearrangement, we provide two global error bounds for the extended vertical linear complementarity problem under the row -property, which extend the error bounds given in Chen and Xiang (Math. Program. 106:513–525, 2006) and Mathias and Pang (Linear Algebra Appl. 132:123–136, 1990) for the P-matrix linear complementarity problem, respectively. We show that one of the new error bounds is sharper than the other, and it can be computed easily for some special class of the row -property block matrix. Numerical examples are given to illustrate the error bounds. The work was in part supported by a Grant-in-Aid from Japan Society for the Promotion of Science, and the National Natural Science Foundation of China (10671010).     

Lawvere Completeness in Topology

It is known since 1973 that Lawvere’s notion of Cauchy-complete enriched category is meaningful for metric spaces: it captures exactly Cauchy-complete metric spaces. In this paper, we introduce the corresponding notion of Lawvere completeness for (\mathbbT,V)(\mathbb{T},\mathsf{V})-categories and show that it has an interesting meaning for topological spaces and quasi-uniform spaces: for the former ones it means weak sobriety while for the latter it means Cauchy completeness. Further, we show that V\mathsf{V} has a canonical (\mathbbT,V)(\mathbb{T},\mathsf{V})-category structure which plays a key role: it is Lawvere-complete under reasonable conditions on the setting; this structure permits us to define a Yoneda embedding in the realm of (\mathbbT,V)(\mathbb{T},\mathsf{V})-categories.     

Fundamentals for symplectic $$ \mathcal{A} $$-modules. Affine Darboux theorem

In his [9–11], the first author shows that the sheaf-theoreti-cally based Abstract Differential Geometry incorporates and generalizes classical differential geometry. Here, we undertake to explore the implications of Abstract Differential Geometry to classical symplectic geometry. The full investigation will be presented elsewhere.      

Quasilinearization and curvature of Aleksandrov spaces

We present a new distance characterization of Aleksandrov spaces of non-positive curvature. By introducing a quasilinearization for abstract metric spaces we draw an analogy between characterization of Aleksandrov spaces and inner product spaces; the quasi-inner product is defined by means of the quadrilateral cosine—a metric substitute for the angular measure between two directions at different points. Our main result states that a geodesically connected metric space is an Aleksandrov domain (also known as a CAT(0) space) if and only if the quadrilateral cosine does not exceed one for every two pairs of distinct points in . We also observe that a geodesically connected metric space is an domain if and only if, for every quadruple of points in , the quadrilateral inequality (known as Euler’s inequality in ) holds. As a corollary of our main result we give necessary and sufficient conditions for a semimetric space to be an domain. Our results provide a complete solution to the Curvature Problem posed by Gromov in the context of metric spaces of non-positive curvature.      

Dirichlet Problem at Infinity for $\mathcal A$-Harmonic Functions

We study the Dirichlet problem at infinity for -harmonic functions on a Cartan–Hadamard manifold M and give a sufficient condition for a point at infinity x ₀∈M(∞) to be -regular. This condition is local in the sense that it only involves sectional curvatures of M in a set U∩M, where U is an arbitrary neighborhood of x ₀ in the cone topology. The results apply to the Laplacian and p-Laplacian, 1<p<∞, as special cases.      

Inverse Conductivity Problem on Riemann Surfaces

An electrical potential U on a bordered Riemann surface X with conductivity function σ>0 satisfies equation d(σ d ^c U)=0. The problem of effective reconstruction of σ from electrical currents measurements (Dirichlet-to-Neumann mapping) on the boundary: U| _bX ↦ σ d ^c U| _bX is studied. We extend to the case of Riemann surfaces the reconstruction scheme given, firstly, by R. Novikov (Funkc. Anal. Ego Priloz. 22:11–22, 2008) for simply connected X. We apply for this new kernels for on the affine algebraic Riemann surfaces constructed in Henkin (, 2008).      

Analysis and Geometry on Worm Domains

In this primarily expository article, we study the analysis of the Diederich-Fornæss worm domain in complex Euclidean space. We review its importance as a domain with nontrivial Nebenhülle, and as a counterexample to a number of basic questions in complex geometric analysis. Then we discuss its more recent significance in the theory of partial differential equations: the worm is the first smoothly bounded, pseudoconvex domain to exhibit global non-regularity for the \(\overline{\partial}\)-Neumann problem. We take this opportunity to prove a few new facts. Next, we turn to specific properties of the Bergman kernel for the worm domain. An asymptotic expansion for this kernel is considered, and applications to function theory and analysis on the worm are provided.     

An algorithm for matching point sets using the l_1 norm

The problem is considered of matching two sets of points in , by translation and rotation. There are many applications, for example in geodesy, computer vision and in the assessment of manufactured parts. When the matching criterion is least squares, there is a well known solution process based on the singular value decomposition of an matrix. Here we consider the use of the norm, which may be more appropriate than least squares in the context of wild points in the data. An algorithm is developed, and is illustrated by some examples for the case .     

$${\mathcal{M}}$$ -decomposability and symmetric unimodal densities in one dimension

In this paper, we introduce the notion of -decomposability of probability density functions in one dimension. Using -decomposability, we derive an inequality that applies to all symmetric unimodal densities. Our inequality involves only the standard deviation of the densities concerned. The concept of -decomposability can be used as a non-parametric criterion for mode-finding and cluster analysis.     

From light tails to heavy tails through multiplier

Let X and Y be two independent nonnegative random variables, of which X has a distribution belonging to the class or for some γ ≥ 0 and Y is unbounded. We study how their product XY inherits the tail behavior of X. Under some mild technical assumptions we prove that the distribution of XY belongs to the class or accordingly. Hence, the multiplier Y builds a bridge between light tails and heavy tails.      

On the Intertwining of \partial{\mathcal{D}}-Isometries

Let be a strictly pseudoconvex bounded domain in with C ² boundary . If a subnormal m-tuple T of Hilbert space operators has the spectral measure of its minimal normal extension N supported on , then T is referred to as a -isometry. Using some non-trivial approximation theorems in the theory of several complex variables, we establish a commutant lifting theorem for those -isometries whose (joint) Taylor spectra are contained in a special superdomain Ω of . Further, we provide a function-theoretic characterization of those subnormal tuples whose Taylor spectra are contained in Ω and that are quasisimilar to a certain (fixed) -isometry T (of which the multiplication tuple on the Hardy space of the unit ball in is a rather special example). Submitted: September 9, 2007. Revised: October 10, 2007. Accepted: October 24, 2007.     

On a sheaf-theoretic version of the Witt’s decomposition theorem. A Lagrangian perspective

The approach to a counterpart, in Abstract Geometric Algebra, that is, Geometric Algebra via sheaves of modules, of the classical Witt’s decomposition theoremis based on the axiomatization of the classical context, which however leads to the formulation of a specific subcategory of the category of sheaves of modules: the full subcategory of convenient sheaves of modules. Convenient sheaves of modules turn out, by the very essence of the matter at hand, to be of further importance as far as the setting of results leading to the sheaf-theoretic aspect of several forms of the Witt’s theorem is concerned. Further versions of the Witt’s theorem are still to be treated elsewhere.      

Generalized Continuous Posets and a New Cartesian Closed Category

With every subset selection for posets, there is associated a certain ideal completion . As shown by Erné, such completions help to extend classical results on domains and similar structures in the absence of the required joins. Some results about –predistributive or –precontinuous posets and –continuous functions are summarized and supplemented. In particular, several central results on function spaces in domain theory are extended to the setting of productive closed subset selections. The category FSBP, in which objects are finitely separated and upper bounded posets and arrows are continuous functions between them, is shown to be cartesian closed. This research is supported by the National Natural Science Foundation of China, 10471035.     

Analysis on adjoint non-recurrent property of nonlinear time series in random environment domain

By introducing a random interference into the typical of nonlinear time series model, this paper establishes a RENLAR model: . The author introduces the definition of adjoint non-recurrence, and utilizing general state space Markov chain theorem, we obtain some criteria for non-recurrence and adjoint non-recurrence of nonlinear time series models in random environment domain and analyze adjoint non-recurrence of some models by using these criteria. Research supported Science Foundation of China (10171009).     

Compactness and local compactness for {\mathbb{R}}-trees

We establish (geometric) criteria for an -tree to be compact and to be locally compact. It follows that locally compact -trees are separable. Received: 10 September 2007     

The G-Fredholm Property of the \bar{\partial} -Neumann Problem

Let G be a unimodular Lie group, X a compact manifold with boundary, and M be the total space of a principal bundle G→M→X so that M is also a strongly pseudoconvex complex manifold. In this work, we show that if G acts by holomorphic transformations in M, then the Laplacian on M has the following properties: The kernel of □ restricted to the forms Λ ^p,q with q>0 is a closed, G-invariant subspace in L ²(M,Λ ^p,q ) of finite G-dimension. Secondly, we show that if q>0, then the image of □ contains a closed, G-invariant subspace of finite G-codimension in L ²(M,Λ ^p,q ). These two properties taken together amount to saying that □ is a G-Fredholm operator. It is a corollary of the first property mentioned that the reduced L ²-Dolbeault cohomology spaces of M are finite G-dimensional for q>0. The boundary Laplacian □ _b has similar properties.      

Endpoint Properties of Localized Riesz Transforms and Fractional Integrals Associated to Schrödinger Operators

Let \({\mathcal L}\equiv-\Delta+V\) be the Schrödinger operator in \({{\mathbb R}^n}\), where V is a nonnegative function satisfying the reverse Hölder inequality. Let ρ be an admissible function modeled on the known auxiliary function determined by V. In this paper, the authors characterize the localized Hardy spaces \(H^1_\rho({{\mathbb R}^n})\) in terms of localized Riesz transforms and establish the boundedness on the BMO-type space \({\mathop\mathrm{BMO_\rho({\mathbb R}^n)}}\) of these operators as well as the boundedness from \({\mathop\mathrm{BMO_\rho({\mathbb R}^n)}}\) to \({\mathop\mathrm{BLO_\rho({\mathbb R}^n)}}\) of their corresponding maximal operators, and as a consequence, the authors obtain the Fefferman–Stein decomposition of \({\mathop\mathrm{BMO_\rho({\mathbb R}^n)}}\) via localized Riesz transforms. When ρ is the known auxiliary function determined by V, \({\mathop\mathrm{BMO_\rho({\mathbb R}^n)}}\) is just the known space \(\mathop\mathrm{BMO}_{\mathcal L}({{\mathbb R}^n})\), and \({\mathop\mathrm{BLO_\rho({\mathbb R}^n)}}\) in this case is correspondingly denoted by \(\mathop\mathrm{BLO}_{\mathcal L}({{\mathbb R}^n})\). As applications, when n?≥?3, the authors further obtain the boundedness on \(\mathop\mathrm{BMO}_{\mathcal L}({{\mathbb R}^n})\) of Riesz transforms \(\nabla{\mathcal L}^{-1/2}\) and their adjoint operators, as well as the boundedness from \(\mathop\mathrm{BMO}_{\mathcal L}({{\mathbb R}^n})\) to \(\mathop\mathrm{BLO}_{\mathcal L}({{\mathbb R}^n})\) of their maximal operators. Also, some endpoint estimates of fractional integrals associated to \({\mathcal L}\) are presented.     

Bounded universal functions in one and several complex variables

We show how to obtain functions that are universal for the ball of , where . The existence of our functions will follow from universality criteria, but we also show how to construct them. Then we study the connection between certain interpolating sequences, runaway automorphisms, and the existence of universal functions on domains in .