All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 3 Next

Displaying 41 – 60 of 67

Showing per page

On the distribution of characteristic parameters of words II

Arturo Carpi, Aldo de Luca (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

The characteristic parameters K w and R w of a word w over a finite alphabet are defined as follows: K w is the minimal natural number such that w has no repeated suffix of length K w and R w is the minimal natural number such that w has no right special factor of length R w . In a previous paper, published on this journal, we have studied the distributions of these parameters, as well as the distribution of the maximal length of a repetition, among the words of each length on a given alphabet. In this paper...

On the distribution of characteristic parameters of words II

Arturo Carpi, Aldo de Luca (2010)

RAIRO - Theoretical Informatics and Applications

The characteristic parameters Kw and Rw of a word w over a finite alphabet are defined as follows: Kw is the minimal natural number such that w has no repeated suffix of length Kw and Rw is the minimal natural number such that w has no right special factor of length Rw. In a previous paper, published on this journal, we have studied the distributions of these parameters, as well as the distribution of the maximal length of a repetition, among the words of each length on a given alphabet....

On ƒ-wise Arc Forwarding Index and Wavelength Allocations in Faulty All-optical Hypercubes

Ján Maňuch, Ladislav Stacho (2010)

RAIRO - Theoretical Informatics and Applications

Motivated by the wavelength division multiplexing in all-optical networks, we consider the problem of finding an optimal (with respect to the least possible number of wavelengths) set of ƒ+1 internally node disjoint dipaths connecting all pairs of distinct nodes in the binary r-dimensional hypercube, where 0 ≤ ƒ < r. This system of dipaths constitutes a routing protocol that remains functional in the presence of up to ƒ faults (of nodes and/or links). The problem of constructing such...

Optimal Locating-Total Dominating Sets in Strips of Height 3

Ville Junnila (2015)

Discussiones Mathematicae Graph Theory

A set C of vertices in a graph G = (V,E) is total dominating in G if all vertices of V are adjacent to a vertex of C. Furthermore, if a total dominating set C in G has the additional property that for any distinct vertices u, v ∈ V C the subsets formed by the vertices of C respectively adjacent to u and v are different, then we say that C is a locating-total dominating set in G. Previously, locating-total dominating sets in strips have been studied by Henning and Jafari Rad (2012). In particular,...

Polypodic codes

Symeon Bozapalidis, Olympia Louscou-Bozapalidou (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Word and tree codes are studied in a common framework, that of polypodes which are sets endowed with a substitution like operation. Many examples are given and basic properties are examined. The code decomposition theorem is valid in this general setup.

Polypodic codes

Symeon Bozapalidis, Olympia Louscou–Bozapalidou (2010)

RAIRO - Theoretical Informatics and Applications

Word and tree codes are studied in a common framework, that of polypodes which are sets endowed with a substitution like operation. Many examples are given and basic properties are examined. The code decomposition theorem is valid in this general setup.

Probabilistic construction of small strongly sum-free sets via large Sidon sets

Andreas Schoen, Tomasz Srivastav, Anand Baltz (2000)

Colloquium Mathematicae

We give simple randomized algorithms leading to new upper bounds for combinatorial problems of Choi and Erdős: For an arbitrary additive group G let P n ( G ) denote the set of all subsets S of G with n elements having the property that 0 is not in S+S. Call a subset A of G admissible with respect to a set S from P n ( G ) if the sum of each pair of distinct elements of A lies outside S. Suppose first that S is a subset of the positive integers in the interval [2n,4n). Denote by f(S) the number of elements in a...

Smooth and sharp thresholds for random k -XOR-CNF satisfiability

Nadia Creignou, Hervé Daudé (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

The aim of this paper is to study the threshold behavior for the satisfiability property of a random k -XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with k variables per equation. For k ≥ 3 we show the existence of a sharp threshold for the satisfiability of a random k -XOR-CNF formula, whereas there are smooth thresholds for k = 1 and k = 2 .

Smooth and sharp thresholds for random {k}-XOR-CNF satisfiability

Nadia Creignou, Hervé Daudé (2010)

RAIRO - Theoretical Informatics and Applications

The aim of this paper is to study the threshold behavior for the satisfiability property of a random k-XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with k variables per equation. For k ≥ 3 we show the existence of a sharp threshold for the satisfiability of a random k-XOR-CNF formula, whereas there are smooth thresholds for k=1 and k=2.

Currently displaying 41 – 60 of 67