Finding K shortest looping paths with waiting time in a time–window network

A time-constrained shortest path problem is a shortest path problem including time constraints that are commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem associated with constraints that are difficult to define or optimize simultaneously. Depending on the types of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence of time–window constraints, waiting time occurs but is largely ignored. Given a network with such constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK²|V₁|³), where r is the number of different windows of a node and |V₁| is the number of nodes in the original network.     

Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999     

On a viscous Hamilton-Jacobi equation with an unbounded potential term

We present comparison, uniqueness and existence results for unbounded solutions of a viscous Hamilton-Jacobi or eikonal equation. The equation includes an unbounded potential term V(x) subject to a quadratic upper bound. The results are obtained through a tailor-made change of variables in combination with the Hopf-Cole transformation. An integral representation formula for the solution of the Cauchy problem is derived in the case where V(x)=ω²|x|²/2.     

Compositions of sums of absolute powers

We obtain an explicit formula for then-dimensional volumes of certain bodies, calledoddballs hereinafter. An oddball is a bodyG = {x εR ⁿ :f(x) ≤ 1}, wheref:R ⁿ →R is anoddball function. Oddball functions are defined by way of the following construction: We begin with the class of functionsf of the formf(x ₁, ...,x _k ) = |x ₁|^α + |x ₂|^β + ... + |x _k|^γ. Herek may be any positive integer, and is not fixed. The Greek exponents are arbitrary positive real numbers. We extend this class by permitting any finite number of substitutions among functions in the class. Finally, we extend the substitution-enlarged class by permitting linear formsy _i = Σ _j b _ij x _j to replacex _i 's, the transformations being nonsingular. Thus, if det(b _ij ) ≠ 0, the oddball function $$f(x_1 ,x_2 ,x_3 ,x_4 ,x_5 ,x_6 ) = ((|y_1 |^\alpha + |y_2 |^\beta )^\tau + (|y_3 |^\gamma + |y_4 |^\phi + |y_5 |^\psi )^\delta )^\mu + |y_6 |^\eta $$ is a fairly typical example. We also consider the number of lattice points in certain types of oddballs, as well as their latticepacking densities. Neither do oddballs include thesuperballs discussed elsewhere by this and other authors, nor is every oddball a superball.     

Stability of Standing Waves for Nonlinear Schrödinger Equations with Inhomogeneous Nonlinearities

The effect of inhomogeneity of nonlinear medium is discussed concerning the stability of standing waves e^{i ω t}ϕ_ω(x) for a nonlinear Schr?dinger equation with an inhomogeneous nonlinearity V (x)|u|^{p − 1}u, where V (x) is proportional to the electron density. Here, ω > 0 and ϕ_ω(x) is a ground state of the stationary problem. When V (x) behaves like |x|^−b at infinity, where 0 < b < 2, we show that e^{i ω t}ϕ_ω(x) is stable for p < 1 + (4 − 2b)/n and sufficiently small ω > 0. The main point of this paper is to analyze the linearized operator at standing wave solution for the case of V (x) = |x|^−b. Then, this analysis yields a stability result for the case of more general, inhomogeneous V (x) by a certain perturbation method. Communicated by Bernard Helffer submitted 14/07/04, accepted 28/02/05     

Richardson's iteration for nonsymmetric matrices

To solve the linear N×N system (1) Ax=a for any nonsingular matrix A, Richardson's iteration (2) x_j+1=x_j-α_j(Ax_j-a), j=1,2,…,n, which is applied in a cyclic manner with cycle length n is investigated, where the α_j are free parameters. The objective is to minimize the error |x_n+1-x|, where x is the solution of (1). If the spectrum of A is known to lie in a compact set S, one is led to the Chebyshev-type approximation problem (3) min_p-1∈Vnmax_z∈S|p(z)|, where V_n is the linear span of z,z²,…,zⁿ. If p solves (3), then the reciprocals of the zeros of p are optimal iteration parameters α_j. It is shown that for a real problem (1) the iteration (2) can be carried out with real arithmetic alone, even when there are complex α_j. The stationary case n=1 is solved completely, i.e., for all compact sets S the problem (3) is solved explicitly. As a consequence, the converging stationary iteration processes can be characterized. For arbitrary closed disks S the problem (3) can be solved for all n∈$\text{N}$, and a simple proof is provided. The lemniscates associated with S are introduced. They appear as an important tool for studying the stability of the iteration (2).     

Removable singularity of the polyharmonic equation

Let x₀∈Ω⊂Rⁿ, n≥2, be a domain and let m≥2. We will prove that a solution u of the polyharmonic equation Δ^mu=0 in Ω?{x₀} has a removable singularity at x₀ if and only if as |x−x₀|→0 for n≥3 and as |x−x₀|→0 for n=2. For m≥2 we will also prove that u has a removable singularity at x₀ if |u(x)|=o(|x−x₀|^2m−n) as |x−x₀|→0 for n≥3 and |u(x)|=o(|x−x₀|^2m−2log(|x−x₀|⁻¹)) as |x−x₀|→0 for n=2.     

Existence of solutions for non-periodic superlinear Schrödinger equations without (AR) condition

The existence of solutions is obtained for a class of the non-periodic Schrödinger equation −Δu + V(x)u = f(x, u), x ∈ R^N, by the generalized mountain pass theorem, where V is large at infinity and f is superlinear as |u| → ∞.     

Solutions of the Robin Problem for the System of Elastic Theory in External Domains

One considers the Robin problem for the linear system of elastic theory. Properties of its solutions are examined in the classes of functions with bounded energy integral with the power weight |x| ^a . For different values of the weight parameter a, uniqueness theorems are proved and exact formulas are obtained for the dimension of the space of solutions of the Robin problem in external domains.     

Directed Graph Pattern Matching and Topological Embedding

Pattern matching in directed graphs is a natural extension of pattern matching in trees and has many applications to different areas. In this paper, we study several pattern matching problems in ordered labeled directed graphs. For the rooted directed graph pattern matching problem, we present an efficient algorithm which, given a pattern graphPand a target graphT, runs in time and spaceO(|E_P| |V_T| + |E_T|). It is faster than the best known method by a factor ofmin{|E_T|, |E_P| |V_T|}. This algorithm can also solve the directed graph pattern matching problem without increasing time or space complexity. Our solution to this problem outperforms the best existing method by Katzenelson, Pinter and Schenfeld by a factor ofmin{|V_P| |E_T|, |V_P| |E_P| |V_T|}. We also present an algorithm for the directed graph topological embedding problem which runs in timeO(|V_P| |E_T| + |E_P|) and spaceO(|V_P| |V_T| + |E_P| + |E_T|). To our knowledge, this algorithm is the first one for this problem.     

Standing waves for supercritical nonlinear Schrödinger equations

Let V(x) be a non-negative, bounded potential in RN, N?3 and p supercritical, . We look for positive solutions of the standing-wave nonlinear Schrödinger equation Δu−V(x)u+up=0 in RN, with u(x)→0 as |x|→+∞. We prove that if V(x)=o(⁻²|x|) as |x|→+∞, then for N?4 and this problem admits a continuum of solutions. If in addition we have, for instance, V(x)=O(|x|^−μ) with μ>N, then this result still holds provided that N?3 and . Other conditions for solvability, involving behavior of V at ∞, are also provided.     

Simultaneous rational approximation to the successive powers of a real number

Let n be an integer ≥ 1 and let θ be a real number which is not an algebraic number of degree ≤ [n/2]. We show that there exist ? > 0 and arbitrary large real numbers X such that the system of linear inequalities |x₀| ≤ X and |x₀θ^j − x_j| ≤ ?X^−1/[n/2] for 1 < j < n, has only the zero solution in rational integers x₀,…, x_n. This result refines a similar statement due to H. Davenport and W. M. Schmidt, where the upper integer part [n/2] is replaced everywhere by the integer part [n/2]. As a corollary, we improve slightly the exponent of approximation to 0 by algebraic integers of degree n + 1 over Q obtained by these authors.     

Fast algorithms for placing large entries along the diagonal of a sparse matrix

Solving a sparse system of linear equations Ax=b is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix A are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix A so that the entries with large absolute values lie on the diagonal has several advantages like better numerical stability for direct methods (e.g., Gaussian elimination) and faster convergence for indirect methods (such as the Jacobi method). Duff (2009) [3] has formulated this as a weighted bipartite matching problem (the MC64 algorithm). In this paper we improve the performance of the MC64 algorithm with a new labeling technique which improves the asymptotic complexity of updating dual variables from O(|V|+|E|) to O(|V|), where |V| is the order of the matrix A and |E| is the number of non-zeros. Experimental results from using the new algorithm, when benchmarked with both industry benchmarks and UFL sparse matrix collection, are very promising. Our algorithm is more than 60 times faster (than Duff’s algorithm) for sparse matrices with at least a million non-zeros.     

Elliptic equation with a singular potential in a domain with a conic point

This paper deals with the behavior of the nonnegative solutions of the problem $$- \Delta u = V(x)u, \left. u \right|\partial \Omega = \varphi (x)$$ in a conical domain Ω ? ? ⁿ , n ≥ 3, where 0 ≤ V (x) ∈ L₁(Ω), 0 ≤ ?(x) ∈ L₁(?Ω) and ?(x) is continuous on the boundary ?Ω. It is proved that there exists a constant C _*(n) = (n ? 2)²/4 such that if V ₀(x) = (c + λ ₁)|x|^?2, then, for 0 ≤ c ≤ C _*(n) and V(x) ≤ V ₀(x) in the domain Ω, this problem has a nonnegative solution for any nonnegative boundary function ?(x) ∈ L ₁(?Ω); for c > C _*(n) and V(x) ≥ V ₀(x) in Ω, this problem has no nonnegative solutions if ?(x) > 0.     

A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees

Let G be a connected simple graph, let X?V (^G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyárfás, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d _T (x) for all x ∈ X, where d _T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d _T (x) ≥ f(x) for all x ∈ X if and only if for any nonempty subset S ? X, |N _G (S) ? S| ? f(S) + 2|S| ? ω _G (S) ≥, where ω _G (S) is the number of components of the subgraph induced by S.     

A generalization of Dirichlet approximation theorem for the affine actions on real line

In this paper, we obtain strong density results for the orbits of real numbers under the action of the semigroup generated by the affine transformations T₀(x)=x/a and T₁(x)=bx+1, where a,b>1. These density results are formulated as generalizations of the Dirichlet approximation theorem and improve the results of Bergelson, Misiurewicz, and Senti. We show that for any x,u>0 there are infinitely many elements γ in the semigroup generated by T₀ and T₁ such that |γ(x)−u|<C(t1/|γ|−1), where C and t are constants independent of γ, and |γ| is the length of γ as a word in the semigroup. Finally, we discuss the problem of approximating an arbitrary real number by the ratios of prime numbers and the ratios of logarithms of prime numbers.     

Compactness results for Schrödinger equations with asymptotically linear terms

We study the nonlinear problem −Δu+V(x)=f(x,u), x∈RN, lim|x|→∞u(x)=0, where the Schrödinger operator −Δ+V is semibounded and the nonlinearity f is linearly bounded. We establish compactness of Palais-Smale sequences and Cerami sequences for the associated energy functional under general spectral-theoretic assumptions. Applying these results, we obtain existence of three nontrivial solutions if the energy functional has a mountain-pass geometry.     

Multiparameter acoustic imaging in the born approximation

Samples of biological tissue are modelled as inhomogeneous fluids with density ?(X) and sound speed c(x) at point x. The samples are contained in the sphere |x| ? δ and it is assumed that ?(x) ? ?₀ = 1 and c(x) ? c₀ = 1 for |x| ? δ, and |γ_n(x)| ? 1 and |?γ?(x)| ? 1 where γ?(x) = ?(x) ? 1 and γ_n(x) = c^?2(x) ? 1. The samples are insonified by plane pulses s(x · θ₀ – t) where x = |θ₀| = 1 and the scattered pulse is shown to have the form |x|^?1 e_s(|x| – t, θ, θ₀) in the far field, where x = |x| θ. The response e_s(τ, θ, θ₀) is measurable. The goal of the work is to construct the sample parameters γn and γ? from e_s(τ, θ, θ₀) for suitable choiches of s, θ and θ₀. In the limiting case of constant density: γ?(x)_? 0 it is shown that Where δ represents the Dirac δ and S² is the unit sphere |θ| = 1. Analogous formulas, based on two sets of measurements, are derived for the case of variable c(x) and ?(x).     

On the decay and scattering for the klein-gordon-hartree equation with radial data

In this paper, we study the decay estimate and scattering theory for the Klein-Gordon-Hartree equation with radial data in space dimension d ≥ 3. By means of a compactness strategy and two Morawetz-type estimates which come from the linear and nonlinear parts of the equation, respectively, we obtain the corresponding theory for energy subcritical and critical cases. The exponent range of the decay estimates is extended to 0 < γ ≤ 4 and γ < d with Hartree potential V (x) = |x|^−γ.     

Critical heat kernel estimates for Schrödinger operators via Hardy-Sobolev inequalities

We obtain Sobolev inequalities for the Shcrödinger operator −Δ−V, where V has critical behaviour V(x)=((N−2)/2)²|x|⁻² near the origin. We apply these inequalities to obtain point-wise estimates on the associated heat kernel, improving upon earlier results.