Search results for "combinatoric"
showing 10 items of 1776 documents
An efficient upper bound of the rotation distance of binary trees
2000
A polynomial time algorithm is developed for computing an upper bound for the rotation distance of binary trees and equivalently for the diagonal-flip distance of convex polygons triangulations. Ordinal tools are used.
Splittings of Toric Ideals
2019
Let $I \subseteq R = \mathbb{K}[x_1,\ldots,x_n]$ be a toric ideal, i.e., a binomial prime ideal. We investigate when the ideal $I$ can be "split" into the sum of two smaller toric ideals. For a general toric ideal $I$, we give a sufficient condition for this splitting in terms of the integer matrix that defines $I$. When $I = I_G$ is the toric ideal of a finite simple graph $G$, we give additional splittings of $I_G$ related to subgraphs of $G$. When there exists a splitting $I = I_1+I_2$ of the toric ideal, we show that in some cases we can describe the (multi-)graded Betti numbers of $I$ in terms of the (multi-)graded Betti numbers of $I_1$ and $I_2$.
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.