A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs

Given an edge-weighted undirected graph G and two prescribed vertices u and v, a next-to-shortest (u,v)-path is a shortest (u,v)-path amongst all (u,v)-paths having length strictly greater than the length of a shortest (u,v)-path. In this paper, we deal with the problem of computing a next-to-shortest (u,v)-path. We propose an O(n²){\mathcal{O}}(n^{2}) time algorithm for solving this problem, which significantly improves the bound of a previous one in O(n³){\mathcal{O}}(n^{3}) time where n is the number of vertices in G.     

Harmonic Wavelet Transform and Image Approximation

In 2006, Saito and Remy proposed a new transform called the Laplace Local Sine Transform (LLST) in image processing as follows. Let f be a twice continuously differentiable function on a domain Ω. First we approximate f by a harmonic function u such that the residual component v=f−u vanishes on the boundary of Ω. Next, we do the odd extension for v, and then do the periodic extension, i.e. we obtain a periodic odd function v ^*. Finally, we expand v ^* into Fourier sine series. In this paper, we propose to expand v ^* into a periodic wavelet series with respect to biorthonormal periodic wavelet bases with the symmetric filter banks. We call this the Harmonic Wavelet Transform (HWT). HWT has an advantage over both the LLST and the conventional wavelet transforms. On the one hand, it removes the boundary mismatches as LLST does. On the other hand, the HWT coefficients reflect the local smoothness of f in the interior of Ω. So the HWT algorithm approximates data more efficiently than LLST, periodic wavelet transform, folded wavelet transform, and wavelets on interval. We demonstrate the superiority of HWT over the other transforms using several standard images.     

Pseudo-cyclic renewal systems

A finite set W of words over an alphabet A is cyclic if, whenever u,v∈A^∗ and uv,vu∈W^∗, we have u,v∈W^∗. If it is only assumed that the property holds for all u,v∈A^∗ with a large length, then W is called pseudo-cyclic, that is, there is N∈N such that, whenever u,v∈A^∗ with |u|, |v|≥N and uv,vu∈W^∗, we have u,v∈W^∗. We analyze the class of pseudo-cyclic sets and describe how it is related to the open question which asks whether every irreducible shift of finite type is conjugate to a renewal system.     

Mixed Discontinuous Galerkin Finite Element Method for the Biharmonic Equation

In this paper, we first split the biharmonic equation Δ² u=f with nonhomogeneous essential boundary conditions into a system of two second order equations by introducing an auxiliary variable v=Δu and then apply an hp-mixed discontinuous Galerkin method to the resulting system. The unknown approximation v _h of v can easily be eliminated to reduce the discrete problem to a Schur complement system in u _h , which is an approximation of u. A direct approximation v _h of v can be obtained from the approximation u _h of u. Using piecewise polynomials of degree p≥3, a priori error estimates of u−u _h in the broken H ¹ norm as well as in L ² norm which are optimal in h and suboptimal in p are derived. Moreover, a priori error bound for v−v _h in L ² norm which is suboptimal in h and p is also discussed. When p=2, the preset method also converges, but with suboptimal convergence rate. Finally, numerical experiments are presented to illustrate the theoretical results. Supported by DST-DAAD (PPP-05) project.     

The Intersection of Two Ringed Surfaces and Some Related Problems

We present an efficient and robust algorithm to compute the intersection curve of two ringed surfaces, each being the sweep ∪_uC^u generated by a moving circle. Given two ringed surfaces ∪_uC^u₁ and ∪_vC^v₂, we formulate the condition C^u₁ ∩ C^v₂ ≠ ∅ (i.e., that the intersection of the two circles C^u₁ and C^v₂ is nonempty) as a bivariate equation λ(u, v)=0 of relatively low degree. Except for redundant solutions and degenerate cases, there is a rational map from each solution of λ(u, v)=0 to the intersection point C^u₁ ∩ C^v₂. Thus it is trivial to construct the intersection curve once we have computed the zero-set of λ(u, v)=0. We also analyze exceptional cases and consider how to construct the corresponding intersection curves. A similar approach produces an efficient algorithm for the intersection of a ringed surface and a ruled surface, which can play an important role in accelerating the ray-tracing of ringed surfaces. Surfaces of linear extrusion and surfaces of revolution reduce their respective intersection algorithms to simpler forms than those for ringed surfaces and ruled surfaces. In particular, the bivariate equation λ(u, v)=0 is reduced to a decomposable form, f(u)=g(v) or 6f(u)−g(v)6=|r(u)|, which can be solved more efficiently than the general case.     

All-Pairs Bottleneck Paths in Vertex Weighted Graphs

Let G=(V,E,w) be a directed graph, where w:V→ℝ is a weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex on the path. For two vertices u,v the capacity from u to v, denoted by c(u,v), is the maximum bottleneck weight of a path from u to v. In the All-Pairs Bottleneck Paths (APBP) problem the task is to find the capacities for all ordered pairs of vertices. Our main result is an O(n ^2.575) time algorithm for APBP. The exponent is derived from the exponent of fast matrix multiplication.     

Improved algorithm for finding next-to-shortest paths

We study the problem of finding the next-to-shortest paths in a weighted undirected graph. A next-to-shortest (u,v)-path is a shortest (u,v)-path amongst (u,v)-paths with length strictly greater than the length of the shortest (u,v)-path. The first polynomial algorithm for this problem was presented in [I. Krasikov, S.D. Noble, Finding next-to-shortest paths in a graph, Inform. Process. Lett. 92 (2004) 117-119]. We improve the upper bound from O(n³m) to O(n³).     

Single display gamut size metric

To measure the relative gamut sizes of wide‐gamut displays, it is herein proposed that the CIE 1931 xy chromaticity diagram be used rather than the nominally perceptually uniform CIE 1976 u′v′ chromaticity diagram. High correlations were found between the area‐coverage ratios in the xy diagram and the volume‐coverage ratios in the CIE 1976 L^*a^*b^* color space for major standard wide‐gamut color spaces. It is also demonstrated herein that performing planimetry in the uniform u′v′ diagram does not yield accurate relative display gamut sizes, even though the large sizes obtained using the u′v′ diagram are often reported regardless of the fact that its uniformity is valid only when the luminance factor is constant. The single display gamut size metric using the xy diagram will facilitate the unbiased development of wide‐gamut displays.     

Rational Solutions of Riccati-like Partial Differential Equations

When factoring linear partial differential systems with a finite-dimensional solution space or analysing symmetries of nonlinear ODEs, we need to look for rational solutions of certain nonlinear PDEs. The nonlinear PDEs are called Riccati-like because they arise in a similar way as Riccati ODEs. In this paper we describe the structure of rational solutions of a Riccati-like system, and an algorithm for computing them. The algorithm is also applicable to finding all rational solutions of Lie’s system { ∂_xu + u² + a₁u + a₂v + a₃, ∂_yu + uv + b₁u + b₂v + b₃, ∂_xv + uv + c₁u + c₂v + c₃, ∂_yv + v² + d₁u + d₂v + d₃},where a₁, . . . , d₃are rational functions of x and y.     

Periods in Extensions of Words

Let π(w) denote the minimum period of the word w,let w be a primitive word with period π(w) < |w|, and let z be a prefix of w. It is shown that if π(wz) = π(w), then |z| < π(w) − gcd (|w|, |z|). Detailed improvements of this result are also proven. Finally, we show that each primitive word w has a conjugate w′ = vu, where w = uv, such that π(w′) = |w′| and |u| < π(w). As a corollary we give a short proof of the fact that if u,v,w are words such that u ² is a prefix of v ², and v ² is a prefix of w ², and v is primitive, then |w| > 2|u|.     

Feedback stabilization of real analytic systems in the plane

We investigate the local feedback stabilization of single input control affine analytic systems in the plane. New necessary and sufficient conditions for local stabilization with feedback laws of the form u = v(x₁,x₂), x2), (v/x₁(0, 0))² + (v/x₁ (0, 0))² 0≠ 0, v(0, 0) = 0, are obtained by using Lyapunov's stability theorems on two-dimensional analytic systems. If the sufficient conditions are satisfied, we also provide explicit feedback laws.     

A note on pure codes

This study extends the understanding of two-element pure codes. Some characteristics of different length two-element pure codes are studied. It is shown that a language is a pure code which contains two distinct primitive words u and v with different lengths if and only if the regular expression u ⁺ v ⁺ of the two distinct words u and v is primitive.     

Ellipse-based principal component analysis for self-intersecting curve reconstruction from noisy point sets

Surface reconstruction from cross cuts usually requires curve reconstruction from planar noisy point samples. The output curves must form a possibly disconnected 1-manifold for the surface reconstruction to proceed. This article describes an implemented algorithm for the reconstruction of planar curves (1-manifolds) out of noisy point samples of a self-intersecting or nearly self-intersecting planar curve C. C:[a,b]⊂R→R ² is self-intersecting if C(u)=C(v), u≠v, u,v∈(a,b) (C(u) is the self-intersection point). We consider only transversal self-intersections, i.e. those for which the tangents of the intersecting branches at the intersection point do not coincide (C′(u)≠C′(v)). In the presence of noise, curves which self-intersect cannot be distinguished from curves which nearly self-intersect. Existing algorithms for curve reconstruction out of either noisy point samples or pixel data, do not produce a (possibly disconnected) Piecewise Linear 1-manifold approaching the whole point sample. The algorithm implemented in this work uses Principal Component Analysis (PCA) with elliptic support regions near the self-intersections. The algorithm was successful in recovering contours out of noisy slice samples of a surface, for the Hand, Pelvis and Skull data sets. As a test for the correctness of the obtained curves in the slice levels, they were input into an algorithm of surface reconstruction, leading to a reconstructed surface which reproduces the topological and geometrical properties of the original object. The algorithm robustly reacts not only to statistical non-correlation at the self-intersections (non-manifold neighborhoods) but also to occasional high noise at the non-self-intersecting (1-manifold) neighborhoods.     

Mathematical Modeling of Textures: Application to Color Image Decomposition with a Projected Gradient Algorithm

In this paper, we are interested in texture modeling with functional analysis spaces. We focus on the case of color image processing, and in particular color image decomposition. The problem of image decomposition consists in splitting an original image f into two components u and v. u should contain the geometric information of the original image, while v should be made of the oscillating patterns of f, such as textures. We propose here a scheme based on a projected gradient algorithm to compute the solution of various decomposition models for color images or vector-valued images. We provide a direct convergence proof of the scheme, and we give some analysis on color texture modeling.     

Adaptive suboptimal control of a linear system with bounded disturbance

An adaptive suboptimal control of a linear discrete system with unknown parameters is proposed. An additive disturbance v_t acting on the system is supposed to be uniformly bounded. The criterion is sup_vtI(y^∞₁, u^∞₁), where y_t is the output, u_t is the control. The adaptive control law gives almost the same guaranteed value of the criterion as the optimal linear feedback does for a system with known parameters.     

A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

We study the partial vertex cover problem. Given a graph G=(V,E), a weight function w:V→R ⁺, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. The problem is clearly NP-hard as it generalizes the well-known vertex cover problem. We provide a primal-dual 2-approximation algorithm which runs in O(nlog n+m) time. This represents an improvement in running time from the previously known fastest algorithm. Our technique can also be used to get a 2-approximation for a more general version of the problem. In the partial capacitated vertex cover problem each vertex u comes with a capacity k _u . A solution consists of a function x:V→ℕ₀ and an orientation of all but s edges, such that the number of edges oriented toward vertex u is at most x _u k _u . Our objective is to find a cover that minimizes ∑ _v∈V x _v w _v . This is the first 2-approximation for the problem and also runs in O(nlog n+m) time. Research supported by NSF Awards CCR 0113192 and CCF 0430650, and the University of Maryland Dean’s Dissertation Fellowship.     

Minimal non-convex words

Using a combinatorial characterization of digital convexity based on words, one defines the language of convex words. The complement of this language forms an ideal whose minimal elements, with respect to the factorial ordering, appear to have a particular combinatorial structure very close to the Christoffel words. In this paper, those words are completely characterized as those of the form uw^kv where k≥1, w=u⋅v and u,v,w are Christoffel words. Also, by considering the most balanced among the unbalanced words, we obtain a second characterization for a special class of minimal non-convex words that are of the form u²v² corresponding to the case k=1 in the previous form.     

A Simple Optimal Parallel Algorithm for a Core of a Tree

A core of a tree T = (V, E) is a path in T which minimizes ∑_vVd(v, P), where d(v, P), the distance from a vertex v to path P, is defined as min_uPd(v, u). We present an optimal parallel algorithm to find a core of T in O(log n) time using O(n/log n) processors on an EREW PRAM machine, where n is the number of vertices of tree T.     

Radio number of ladder graphs

Let G be a connected graph with diameter diam(G). The radio number for G, denoted by rn(G), is the smallest integer k such that there exists a function f: V(G)→{0, 1, 2, …, k} with the following satisfied for all vertices u and v:|f(u)?f(v)|≥diam (G)?d _G (u, v)+1, where d _G (u, v) is the distance between u and v in G. In this paper, we determine the radio number of ladder graphs.