The super spanning connectivity and super spanning laceability of the enhanced hypercubes

A k -container C(u,v) of a graph G is a set of k disjoint paths between u and v. A k-container C(u,v) of G is a k ^* -container if it contains all vertices of G. A graph G is k ^* -connected if there exists a k ^*-container between any two distinct vertices of G. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is Hamiltonian connected (respectively, Hamiltonian). A graph G is super spanning connected if there exists a k ^*-container between any two distinct vertices of G for every k with 1≤k≤κ(G) where κ(G) is the connectivity of G. A bipartite graph G is k ^* -laceable if there exists a k ^*-container between any two vertices from different partite set of G. A bipartite graph G is super spanning laceable if there exists a k ^*-container between any two vertices from different partite set of G for every k with 1≤k≤κ(G). In this paper, we prove that the enhanced hypercube Q _n,m is super spanning laceable if m is an odd integer and super spanning connected if otherwise.

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.     

Constructing Labeling Schemes through Universal Matrices

Let f be a function on pairs of vertices. An f -labeling scheme for a family of graphs ℱ labels the vertices of all graphs in ℱ such that for every graph G∈ℱ and every two vertices u,v∈G, f(u,v) can be inferred by merely inspecting the labels of u and v. The size of a labeling scheme is the maximum number of bits used in a label of any vertex in any graph in ℱ. This paper illustrates that the notion of universal matrices can be used to efficiently construct f-labeling schemes.     

New Plain-Exponential Time Classes for Graph Homomorphism

A homomorphism from a graph G to a graph H (in this paper, both simple, undirected graphs) is a mapping f:V(G)→V(H) such that if uv∈E(G) then f(u)f(v)∈E(H). The problem Hom (G,H) of deciding whether there is a homomorphism is NP-complete, and in fact the fastest known algorithm for the general case has a running time of O ^*(n(H) ^cn(G)) (the notation O ^*(⋅) signifies that polynomial factors have been ignored) for a constant 0<c<1. In this paper, we consider restrictions on the graphs G and H such that the problem can be solved in plain-exponential time, i.e. in time O ^*(c ^n(G)+n(H)) for some constant c.     

Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits

We consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates. We define the entropy of an operator f:{0,1} ⁿ →{0,1} ^m as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Our main result is that every depth-2 circuit for f requires at least entropy(f) wires. This is reminiscent of a classical lower bound of Nechiporuk on the formula size, and gives an information-theoretic explanation of why some operators require many wires. We use this to prove a tight estimate Θ(n ³) of the smallest number of wires in any depth-2 circuit computing the product of two n by n matrices over any finite field. Previously known lower bound for this operator was Ω(n ²log n).     

(Φ,Φ<Superscript>*</Superscript>) Image Decomposition Models and Minimization Algorithms

We propose in this paper minimization algorithms for image restoration using dual functionals and dual norms. In order to extract a clean image u from a degraded version f=Ku+n (where f is the observation, K is a blurring operator and n represents additive noise), we impose a standard regularization penalty Φ(u)=∫ φ(|Du|)dx<∞ on u, where φ is positive, increasing and has at most linear growth at infinity. However, on the residual f−Ku we impose a dual penalty Φ^*(f−Ku)<∞, instead of the more standard fidelity term. In particular, when φ is convex, homogeneous of degree one, and with linear growth (for instance the total variation of u), we recover the (BV,BV ^*) decomposition of the data f, as suggested by Y. Meyer (Oscillating Patterns in Image Processing and Nonlinear Evolution Equations, University Lecture Series, vol. 22, Am. Math. Soc., Providence, 2001). Practical minimization methods are presented, together with theoretical, experimental results and comparisons to illustrate the validity of the proposed models. Moreover, we also show that by a slight modification of the associated Euler-Lagrange equations, we obtain well-behaved approximations and improved results.

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.     

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.     

Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs

The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ε > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (ku, kl), our algorithm constructs a vertex cover of size (ku*, kl* ), satisfying max{ku*/ku, kl* /kl} 1 ε.     

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.     

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.     

Risoluzione numerica di una disequazione variazionale

Riassunto Sia Ω un insieme aperto, connesso e limitato dello spazio euclideo reale adn dimensioni ℝ ⁿ . Sia ψ una funzione reale definita sulla chinsura di Ω e non positiva in prossimità della frontiera Γ di Ω. Presentiamo un metodo per la risoluzione numerica della disequazione variazionale dove ℝ={u∈H ₀ ¹ (Ω)|u≥ψ su ea(u, v) è una forma bilineare coercitiva sul sottospazioH ₀ ¹ (Ω) dello spazio reale di SobolevH ¹ (Ω).

---

Let Ω be an open, connected and bounded set of then-dimensional real Euclidean space ℝ ⁿ . Let ψ be a real function defined on the closure of Ω and non-positive near the boundary of Ω. We present a method for the numerical solution of the variational inequality where ℝ={u∈H ₀ ¹ (Ω)|u≥ψ on anda(u, v) is a bilinear form coercive on the subspaceH ₀ ¹ (Ω) of the real Sobolev spaceH ¹ (Ω).

     

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|.     

A Property Tester for Tree-Likeness of Quartet Topologies

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property ℘ and a parameter 0<ε<1, by examining function values of f over o(|D|) elements in D, determine whether f satisfies ℘ or differs from any one which satisfies ℘ in at least ε|D| elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f _Q , which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that f _Q satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f _Q . In this paper, we prove the existence of a set of quartet topologies of error number at least c((n) || 4)c{n\choose 4} for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O(n ³/ε) queries, and is of one-sided error and non-adaptive.     

A penalty method for the approximation of projections over cones in Hilbert spaces

Given a closed convex coneK in a Hilbert spaceH and a vectoru ₀ ∈H, a penalty method is built up in order to approximate the projection ofu ₀ over the polar coneK ^* ofK, without making use of the inverse transform of the canonical mapping ofH into its dual spaceH′. Such method is outlined in n⁰ 1, 2. In n⁰3 a complete analysis of the errors of the method is explained. In n⁰4 the method is applied to find error bounds for the numerical approximation of the projection ofu ₀ onK.     

Convergence with a fixed regulator in lattice ordered groups and applications to MV-algebras

A convergence with a fixed regulator v in lattice ordered groups is applied to MV-algebras. For each Archimedean MV-algebra A there exists a v-Cauchy completion A ^* and it is uniquely determined up to isomorphisms over A. The relation between the Dedekind completion A ^∧ of A and A ^* is established. There is solved a question of the existence of the greatest v-Cauchy complete ideal of A.     

A New view of the approximations in H v -groups

Let H is an H _v -group and the set of all finite products of elements of H. The relation β^* is the smallest equivalence relation on H such that the quotient H/ β^* is a group. The relation β^* is transitive closure of the relation β, where β is defined as follows: x β y if and only if for some . Based on the relation β, we define a neighborhood system for each element of H, and we presents a general framework for the study of approximations in H _v -groups. In construction approach, a pair of lower and upper approximation operators is defined. The connections between H _v -groups and approximation operators are examined.     

Not necessarily proper total colourings which are adjacent vertex distinguishing

Let G be a simple graph with no isolated edge. Let f be a total colouring of G which is not necessarily proper. f is said to be adjacent vertex distinguishing if for any pair of adjacent vertices u, v of G, we have C(u)≠C(v), where C(u) denotes the set of colours of u and its incident edges under f. The minimum number of colours required for an adjacent vertex distinguishing not necessarily proper total colouring of G is called the adjacent vertex distinguishing not necessarily proper total chromatic number. Seven kinds of adjacent vertex distinguishing not necessarily proper total colourings are introduced in this paper. Some results of adjacent vertex distinguishing not necessarily proper total chromatic numbers are obtained and some conjectures are also proposed.     

The Complexity of Boolean Functions in Different Characteristics

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0, 1}ⁿ → {0, 1} which depend on all n variables, and distinct primes p, q:

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.