Search results for "Combinatorics"
showing 10 items of 1770 documents
On the lattice of prefix codes
2002
AbstractThe natural correspondence between prefix codes and trees is explored, generalizing the results obtained in Giammarresi et al. (Theoret. Comput. Sci. 205 (1998) 1459) for the lattice of finite trees under division and the lattice of finite maximal prefix codes. Joins and meets of prefix codes are studied in this light in connection with such concepts as finiteness, maximality and varieties of rational languages. Decidability results are obtained for several problems involving rational prefix codes, including the solution to the primeness problem.
Uniqueness of diffusion on domains with rough boundaries
2016
Let $\Omega$ be a domain in $\mathbf R^d$ and $h(\varphi)=\sum^d_{k,l=1}(\partial_k\varphi, c_{kl}\partial_l\varphi)$ a quadratic form on $L_2(\Omega)$ with domain $C_c^\infty(\Omega)$ where the $c_{kl}$ are real symmetric $L_\infty(\Omega)$-functions with $C(x)=(c_{kl}(x))>0$ for almost all $x\in \Omega$. Further assume there are $a, \delta>0$ such that $a^{-1}d_\Gamma^{\delta}\,I\le C\le a\,d_\Gamma^{\delta}\,I$ for $d_\Gamma\le 1$ where $d_\Gamma$ is the Euclidean distance to the boundary $\Gamma$ of $\Omega$. We assume that $\Gamma$ is Ahlfors $s$-regular and if $s$, the Hausdorff dimension of $\Gamma$, is larger or equal to $d-1$ we also assume a mild uniformity property for $\Omega$ i…
Time-dependent asymmetric traveling salesman problem with time windows: Properties and an exact algorithm
2019
Abstract In this paper, we deal with the Time-Dependent Asymmetric Traveling Salesman Problem with Time Windows. First, we prove that under special conditions the problem can be solved as an Asymmetric Traveling Salesman Problem with Time Windows, with suitable-defined time windows and (constant) travel times. Second, we show that, if the special conditions do not hold, the time-independent optimal solution provides both a lower bound and (eventually) an upper bound with a worst-case guarantee for the Time-Dependent Asymmetric Traveling Salesman Problem with Time Windows. Finally, a branch-and-bound algorithm is presented and tested on a set of 4800 instances. The results have been compared…
A branch-and-price framework for decomposing graphs into relaxed cliques
2021
We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property—for example, the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices—is relaxed. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease-spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new, effective pricing algorithms are developed, and new…
The validity of the “liminf” formula and a characterization of Asplund spaces
2014
Abstract We show that for a given bornology β on a Banach space X the following “ lim inf ” formula lim inf x ′ ⟶ C x T β ( C ; x ′ ) ⊂ T c ( C ; x ) holds true for every closed set C ⊂ X and any x ∈ C , provided that the space X × X is ∂ β -trusted. Here T β ( C ; x ) and T c ( C ; x ) denote the β-tangent cone and the Clarke tangent cone to C at x. The trustworthiness includes spaces with an equivalent β-differentiable norm or more generally with a Lipschitz β-differentiable bump function. As a consequence, we show that for the Frechet bornology, this “ lim inf ” formula characterizes in fact the Asplund property of X. We use our results to obtain new characterizations of T β -pseudoconve…
Rotation topological factors of minimal $\mathbb {Z}^{d}$-actions on the Cantor set
2006
In this paper we study conditions under which a free minimal Z d -action on the Cantor set is a topological extension of the action of d rotations, either on the product T d of d 1-tori or on a single 1-torus T 1 . We extend the notion of linearly recurrent systems defined for Z-actions on the Cantor set to Z d -actions, and we derive in this more general setting a necessary and sufficient condition, which involves a natural combinatorial data associated with the action, allowing the existence of a rotation topological factor of one of these two types.
A continuous decomposition of the Menger curve into pseudo-arcs
2000
It is proved that the Menger universal curve M admits a continuous decomposition into pseudo-arcs with the quotient space homeomorphic to M. Wilson proved [8] Anderson's announcement [1] saying that for any Peano continuum X the Menger universal curve M admits a continuous decomposition into homeomorphic copies of M such that the quotient space is homeomorphic to X. Anderson also announced (unpublished) that the plane admits a continuous decomposition into pseudo-arcs. This result was proved by Lewis and Walsh [4]. In a previous paper [6] the author has proved that each locally planar Peano continuum with no local separating point admits a continuous decomposition into pseudo-arcs. Applying…
IFS attractors and Cantor sets
2006
Abstract We build a metric space which is homeomorphic to a Cantor set but cannot be realized as the attractor of an iterated function system. We give also an example of a Cantor set K in R 3 such that every homeomorphism f of R 3 which preserves K coincides with the identity on K.
Generalized centro-invertible matrices with applications
2014
Centro-invertible matrices are introduced by R.S. Wikramaratna in 2008. For an involutory matrix R, we define the generalized centro-invertible matrices with respect to R to be those matrices A such that RAR = A^−1. We apply these matrices to a problem in modular arithmetic. Specifically, algorithms for image blurring/deblurring are designed by means of generalized centro-invertible matrices. In addition, if R1 and R2 are n × n involutory matrices, then there is a simple bijection between the set of all centro-invertible matrices with respect to R1 and the set with respect to R2.
Further monotonicity and convexity properties of the zeros of cylinder functions
1992
AbstractLet cvk be the kth positive zero of the cylinder function Cv(x,α)=Jv(x) cos α−Yv sin α, 0⩽α<π, where Jv(x) and Yv(x) are the Bessel functions of the first and the second kind, respectively. We prove that the function v(d2cvkddv2+δ)cvk increases with v⩾0 for suitable values of δ and k−απ⩾ 0.7070… . From this result under the same conditions we deduce, among other things, that cvk+12δv2 is convex as a function of v⩾0. Moreover, we show some monotonicity properties of the function c2vkv. Our results improve known results.