Search results for "combinatorics"
showing 10 items of 1770 documents
Dynamic 2- and 3-connectivity on planar graphs
1992
We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total of O(n log n) time under any sequence of at most O(n) deletions. This gives O(log n) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O(n log2n) time. This gives O(log2n) amortized time per deletion. The space required by all our data structures is O(n).
On Combinatorial Generation of Prefix Normal Words
2014
A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present an efficient algorithm for exhaustively listing the prefix normal words with a fixed length. The algorithm is based on the fact that the language of prefix normal words is a bubble language, a class of binary languages with the property that, for any word w in the language, exchanging the first occurrence of 01 by 10 in w results in another word in the language. We prove that each prefix normal word is produced in O(n) amortized time, and conjecture, based on expe…
Effects of power resistance training program with elastic bands on body composition, muscle strength and physical function in older women
2020
The aim of this study was to investigate the effects of a power-strength resistance program with elastic bands on body composition, physical function, and muscle strength in older women. For such purpose, a randomized controlled trial with a pre-post-intervention design was conducted. Thus, 58 healthy, physically independent, sedentary women, aged 65-85 years, were randomly allocated to the intervention (n = 28) or control group (n = 30). Measurements of body composition (total mass, total fat mass, total skeletal-muscle mass, and body fat percentage), isokinetic muscle strength of knee flexors and extensors (at 60º/second and 180º/second), and physical performance (flexibility, agility/dyn…
QSAR Modeling ANTI-HIV-1 Activities by Optimization of Correlation Weights of Local Graph Invariants
2004
Results of using descriptors calculated with the correlation weights (CWs) of local graph invariants for modeling of anti-HIV-1 potencies of two groups of reverse transcriptase (RT) inhibitors are reported. Presence of different chemical elements in molecular structure of the inhibitors and the presence of Morgan extended connectivity values of zeroth-, first- and second order have been examined as local graph invariants in the labeled hydrogen-filled graphs. By Monte Carlo method optimization procedure, values of the CWs which produce as large values as possible of correlation coefficient between the numerical data on the anti-HIV-1 potencies and values of the descriptors on the training s…
Multiple normalized solutions for a Sobolev critical Schrödinger-Poisson-Slater equation
2021
We look for solutions to the Schr\"{o}dinger-Poisson-Slater equation $$- \Delta u + \lambda u - \gamma (|x|^{-1} * |u|^2) u - a |u|^{p-2}u = 0 \quad \text{in} \quad \mathbb{R}^3, $$ which satisfy \begin{equation*} \int_{\mathbb{R}^3}|u|^2 \, dx = c \end{equation*} for some prescribed $c>0$. Here $ u \in H^1(\mathbb{R}^3)$, $\gamma \in \mathbb{R},$ $ a \in \mathbb{R}$ and $p \in (\frac{10}{3}, 6]$. When $\gamma >0$ and $a > 0$, both in the Sobolev subcritical case $p \in (\frac{10}{3}, 6)$ and in the Sobolev critical case $p=6$, we show that there exists a $c_1>0$ such that, for any $c \in (0,c_1)$, the equation admits two solutions $u_c^+$ and $u_c^-$ which can be characterized respectively…
Lipschitz-type conditions on homogeneous Banach spaces of analytic functions
2017
Abstract In this paper we deal with Banach spaces of analytic functions X defined on the unit disk satisfying that R t f ∈ X for any t > 0 and f ∈ X , where R t f ( z ) = f ( e i t z ) . We study the space of functions in X such that ‖ P r ( D f ) ‖ X = O ( ω ( 1 − r ) 1 − r ) , r → 1 − where D f ( z ) = ∑ n = 0 ∞ ( n + 1 ) a n z n and ω is a continuous and non-decreasing weight satisfying certain mild assumptions. The space under consideration is shown to coincide with the subspace of functions in X satisfying any of the following conditions: (a) ‖ R t f − f ‖ X = O ( ω ( t ) ) , (b) ‖ P r f − f ‖ X = O ( ω ( 1 − r ) ) , (c) ‖ Δ n f ‖ X = O ( ω ( 2 − n ) ) , or (d) ‖ f − s n f ‖ X = O ( ω …
Binary Hamming codes and Boolean designs
2021
AbstractIn this paper we consider a finite-dimensional vector space $${\mathcal {P}}$$ P over the Galois field $${\text {GF}}(2),$$ GF ( 2 ) , and the family $${\mathcal {B}}_k$$ B k (respectively, $${\mathcal {B}}_k^*$$ B k ∗ ) of all the k-sets of elements of $$\mathcal {P}$$ P (respectively, of $${\mathcal {P}}^*= {\mathcal {P}} \setminus \{0\}$$ P ∗ = P \ { 0 } ) summing up to zero. We compute the parameters of the 3-design $$({\mathcal {P}},{\mathcal {B}}_k)$$ ( P , B k ) for any (necessarily even) k, and of the 2-design $$({\mathcal {P}}^{*},{\mathcal {B}}_k^{*})$$ ( P ∗ , B k ∗ ) for any k. Also, we find a new proof for the weight distribution of the binary Hamming code. Moreover, we…
Linear and cyclic radio k-labelings of trees
2007
International audience; Motivated by problems in radio channel assignments, we consider radio k-labelings of graphs. For a connected graph G and an integer k ≥ 1, a linear radio k-labeling of G is an assignment f of nonnegative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two distinct vertices x and y, where dG(x,y) is the distance between x and y in G. A cyclic k-labeling of G is defined analogously by using the cyclic metric on the labels. In both cases, we are interested in minimizing the span of the labeling. The linear (cyclic, respectively) radio k-labeling number of G is the minimum span of a linear (cyclic, respectively) radio k-labeling of G. In this p…
Hölder stability for Serrin’s overdetermined problem
2015
In a bounded domain \(\varOmega \), we consider a positive solution of the problem \(\Delta u+f(u)=0\) in \(\varOmega \), \(u=0\) on \(\partial \varOmega \), where \(f:\mathbb {R}\rightarrow \mathbb {R}\) is a locally Lipschitz continuous function. Under sufficient conditions on \(\varOmega \) (for instance, if \(\varOmega \) is convex), we show that \(\partial \varOmega \) is contained in a spherical annulus of radii \(r_i 0\) and \(\tau \in (0,1]\). Here, \([u_\nu ]_{\partial \varOmega }\) is the Lipschitz seminorm on \(\partial \varOmega \) of the normal derivative of u. This result improves to Holder stability the logarithmic estimate obtained in Aftalion et al. (Adv Differ Equ 4:907–93…
Sturmian words and overexponential codimension growth
2018
Abstract Let A be a non necessarily associative algebra over a field of characteristic zero satisfying a non-trivial polynomial identity. If A is a finite dimensional algebra or an associative algebra, it is known that the sequence c n ( A ) , n = 1 , 2 , … , of codimensions of A is exponentially bounded. If A is an infinite dimensional non associative algebra such sequence can have overexponential growth. Such phenomenon is present also in the case of Lie or Jordan algebras. In all known examples the smallest overexponential growth of c n ( A ) is ( n ! ) 1 2 . Here we construct a family of algebras whose codimension sequence grows like ( n ! ) α , for any real number α with 0 α 1 .