Pascal Ochem, Elise Vaslet (2012)
RAIRO - Theoretical Informatics and Applications
Similarity:
The introduced by Dejean and Brandenburg is the smallest real number such that there exists an infinite word over a -letter alphabet that avoids -powers for all . We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.
Jair Donadelli, Penny E. Haxell, Yoshiharu Kohayakawa (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
Let be the graph obtained from a given graph by subdividing each edge times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in (SODA 2002) 321–328], we prove that, for any graph , there exist graphs with edges that are Ramsey with respect to .
Giuseppe Buttazzo, Berardo Ruffini, Bozhidar Velichkov (2014)
ESAIM: Control, Optimisation and Calculus of Variations
Similarity:
): ∈ 𝒜, ℋ() = }, where ℋ ,, } ⊂ R . The cost functional ℰ() is the Dirichlet energy of defined through the Sobolev functions on vanishing on the points . We analyze the existence of a solution in both the families of connected sets and of metric graphs. At the end, several explicit examples are discussed.
Lan Lin, Yixun Lin (2011)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
The bandwidth minimization problem is of significance in network communication and related areas. Let be a graph of vertices. The two-dimensional bandwidth () of is the minimum value of the maximum distance between adjacent vertices when is embedded into an × grid in the plane. As a discrete optimization problem, determining () is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This...
Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When =1 we show that . In the cases when or max} we show that the first difference of the complexity function takes value in for every , and consequently we determine...
Arturo Carpi, Aldo de Luca (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
For any finite word on a finite alphabet, we consider the basic parameters and of defined as follows: is the minimal natural number for which has no right special factor of length and is the minimal natural number for which has no repeated suffix of length . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words ...
Jing Dong, Qinghui Liu (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
The infinite Post Correspondence Problem (PCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [36 (2003) 231–245] showed that PCP is undecidable for domain alphabets of size 105, Halava and Harju [40 (2006) 551–557] showed that PCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju’s construction. So we prove that PCP is undecidable for domain alphabets of size 8.