Calcul pratique du treillis de Galois d'une correspondance
Canonical decomposition of outerplanar maps and application to enumeration, coding and generation.
Canonical greedy algorithms and dynamic programming
Census algorithms for chinese remainder pseudorank
We investigate the density and distribution behaviors of the chinese remainder representation pseudorank. We give a very strong approximation to density, and derive two efficient algorithms to carry out an exact count (census) of the bad pseudorank integers. One of these algorithms has been implemented, giving results in excellent agreement with our density analysis out to -bit integers.
Census algorithms for chinese remainder pseudorank
We investigate the density and distribution behaviors of the chinese remainder representation pseudorank. We give a very strong approximation to density, and derive two efficient algorithms to carry out an exact count (census) of the bad pseudorank integers. One of these algorithms has been implemented, giving results in excellent agreement with our density analysis out to 5189-bit integers.
Certificates of factorisation for a class of triangle-free graphs.
Certificates of factorisation for chromatic polynomials.
Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs.
Characteristic sets of a system of equivalence relations
Characterization of substitution invariant words coding exchange of three intervals.
Characterizations of words with many periods.
Characterizing families of cuts that can be represented by axis-parallel rectangles.
Clustering cycles into cycles of clusters.
Clustering in trees: Optimizing cluster sizes and number of subtrees.
Cobham's theorem for substitutions
The seminal theorem of Cobham has given rise during the last 40 years to a lot of work about non-standard numeration systems and has been extended to many contexts. In this paper, as a result of fifteen years of improvements, we obtain a complete and general version for the so-called substitutive sequences. Let and be two multiplicatively independent Perron numbers. Then a sequence , where is a finite alphabet, is both -substitutive and -substitutive if and only if is ultimately periodic....
Collective tree spanners and routing in AT-free related graphs.
Combinatoire de mots récurrents de complexité n+2
Nous établissons quelques propriétés des mots sturmiens et classifions, ensuite, les mots infinis qui possèdent, pour tout entier naturel non nul n, exactement n+2 facteurs de longueur n. Nous définissons également la notion d'insertion k à k sur les mots infinis puis nous calculons la complexité des mots obtenus en appliquant cette notion aux mots sturmiens. Enfin nous étudions l'équilibre et la palindromie d'une classe particulière de mots de complexité n+2 que nous appelons mots quasi-sturmiens...
Combinatoire des codages de rotations
Combinatorial and arithmetical properties of infinite words associated with non-simple quadratic Parry numbers
We study some arithmetical and combinatorial properties of β-integers for β being the larger root of the equation x2 = mx - n,m,n ∈ ℵ, m ≥ n +2 ≥ 3. We determine with the accuracy of ± 1 the maximal number of β-fractional positions, which may arise as a result of addition of two β-integers. For the infinite word uβ> coding distances between the consecutive β-integers, we determine precisely also the balance. The word uβ> is the only fixed point of the morphism A → Am-1B and B → Am-n-1B. In...
Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers