Search results for "Integer"
showing 10 items of 250 documents
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…
A new compact formulation for the discrete p-dispersion problem
2017
Abstract This paper addresses the discrete p -dispersion problem (PDP) which is about selecting p facilities from a given set of candidates in such a way that the minimum distance between selected facilities is maximized. We propose a new compact formulation for this problem. In addition, we discuss two simple enhancements of the new formulation: Simple bounds on the optimal distance can be exploited to reduce the size and to increase the tightness of the model at a relatively low cost of additional computation time. Moreover, the new formulation can be further strengthened by adding valid inequalities. We present a computational study carried out over a set of large-scale test instances i…
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$.
Iterative sparse matrix-vector multiplication for accelerating the block Wiedemann algorithm over GF(2) on multi-graphics processing unit systems
2012
SUMMARY The block Wiedemann (BW) algorithm is frequently used to solve sparse linear systems over GF(2). Iterative sparse matrix–vector multiplication is the most time-consuming operation. The necessity to accelerate this step is motivated by the application of BW to very large matrices used in the linear algebra step of the number field sieve (NFS) for integer factorization. In this paper, we derive an efficient CUDA implementation of this operation by using a newly designed hybrid sparse matrix format. This leads to speedups between 4 and 8 on a single graphics processing unit (GPU) for a number of tested NFS matrices compared with an optimized multicore implementation. We further present…
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.
Languages with mismatches
2007
AbstractIn this paper we study some combinatorial properties of a class of languages that represent sets of words occurring in a text S up to some errors. More precisely, we consider sets of words that occur in a text S with k mismatches in any window of size r. The study of this class of languages mainly focuses both on a parameter, called repetition index, and on the set of the minimal forbidden words of the language of factors of S with errors. The repetition index of a string S is defined as the smallest integer such that all strings of this length occur at most in a unique position of the text S up to errors. We prove that there is a strong relation between the repetition index of S an…
Extremal Frobenius numbers in a class of sets
1998
For given $ A_k=\{ a_1,\ldots ,a_k \}, a_1 \le \ldots \le a_k $ coprime the Frobenius number $ {g}(A_k) $ is defined as the greatest integer ${g}$ with no representation¶¶ ${g}=\sum \limits ^k_{i=1}\,x_i\,a_i,\;x_i\in {\Bbb N}_0 $ . ¶¶A class $ {\bf A}^*_k $ is given, such that ¶¶ $ {\overline {g}}^*(k,y):= \max \{ {g}(A_k)|A_k\in {\bf A}^*_k,\, a_k\le y \} $ ¶¶has the same asymptotic behaviour as the general function¶¶ $ {\overline {g}}(k,y):= \max \{ {g}(A_k)| a_k\le y \}\, {\rm for} \, y\to \infty $ .¶¶ Furthermore, ¶¶ $ {\underline {g}}^*(k,x):= \min \{ {g}(A_k)|A_k\in {\bf A}^*_k,\, a_1\ge x \} $ ¶¶is shown to have the same order of magnitude as the general function¶¶ $ {\underline {g}…
Asymptotics for thenth-degree Laguerre polynomial evaluated atn
1992
We investigate the asymptotic behaviour of ? n (n),n?? where ? n (x) denotes the Laguerre polynomial of degreen. Our results give a partial answer to the conjecture ?? n (n)>1 forn>6, made in 1984 by van Iseghem. We also show the connection between this conjecture and the continued fraction approximants of $$6\sqrt {{3 \mathord{\left/ {\vphantom {3 \pi }} \right. \kern-\nulldelimiterspace} \pi }} $$ .
Homogeneous products of characters
2004
I. M. Isaacs has conjectured (see \cite{isa00}) that if the product of two faithful irreducible characters of a solvable group is irreducible, then the group is cyclic. In this paper we prove a special case of the following conjecture, which generalizes Isaacs conjecture. Suppose that $G$ is solvable and that $\psi,\phi\in\Irr(G)$ are faithful. If $\psi \phi=m\chi$ where $m$ is a positive integer and $\chi \in \Irr(G)$ then $\psi$ and $\phi$ vanish on $G- Z(G)$. In particular we prove that the above conjecture holds for $p$-groups.
Integer Complexity: Experimental and Analytical Results II
2015
We consider representing natural numbers by expressions using only 1’s, addition, multiplication and parentheses. Let \( \left\| n \right\| \) denote the minimum number of 1’s in the expressions representing \(n\). The logarithmic complexity \( \left\| n \right\| _{\log } \) is defined to be \({ \left\| n \right\| }/{\log _3 n}\). The values of \( \left\| n \right\| _{\log } \) are located in the segment \([3, 4.755]\), but almost nothing is known with certainty about the structure of this “spectrum” (are the values dense somewhere in the segment?, etc.). We establish a connection between this problem and another difficult problem: the seemingly “almost random” behaviour of digits in the ba…