Fimmel, Elena Michel, Christian Pirot, François Sereni, Jean-Sébastien Strüngmann, Lutz

By an extensive statistical analysis in genes of bacteria, archaea, eukaryotes, plasmids and viruses, a maximal C3-self-complementary trinucleotide circular code has been found to have the highest average occurrence in the reading frame of the ribosome during translation. Circular codes may play an important role in maintaining the correct reading ...

Flores-Luyo, Luis Agra, Agostinho Figueiredo, Rosa Ocana, Eladio

We study a routing-collecting problem where a system of stations is considered. A vehicle is responsible for collecting information generated continuously in the stations and to deliver it to the base station. The objective is to determine the vehicle route and the collection operations, both physical and wireless, in order to maximize the amount o...

Ducoffe, Guillaume Marinescu-Ghemeci, Ruxandra Popa, Alexandru

The (directed) proper connection number of a given (di)graph G is the least number of colors needed to edge-color G such that there exists a properly colored (di)path between every two vertices in G. There also exist vertex-coloring versions of the proper connection number in (di)graphs. We initiate the study of the complexity of computing the prop...

Bousquet, Nicolas Lochet, William Thomassé, Stéphan

A very nice result of Bárány and Lehel asserts that every finite subset X or can be covered by X-boxes (i.e. each box has two antipodal points in X). As shown by Gyárfás and Pálvőlgyi this result would follow from the following conjecture: If a tournament admits a partition of its arc set into k quasi-orders, then its domination number is bounded i...

Meyer, Luc Ichalal, Dalil Vigneron, Vincent

This paper investigates the construction of an estimator for switching linear systems with unknown inputs (UI) and Gaussian noises, in the case of unknown switching sequence. First, a maximum-likelihood switching sequence estimator is constructed. Then, both state and UI estimators are proposed. An example illustrates the theoretical contributions....

Gravier, Sylvain Heinrich, Marc

Greedy algorithms for the graph coloring problem require a large number of colors, even for very simple classes of graphs. For example, any greedy algorithm coloring trees requires Ω(log n) colors in the worst case. We consider a variation of greedy algorithms in which the algorithm is allowed to make modifications to previously colored vertices by...

Gravier, Sylvain Heinrich, Marc

Greedy algorithms for the graph coloring problem require a large number of colors, even for very simple classes of graphs. For example, any greedy algorithm coloring trees requires Ω(log n) colors in the worst case. We consider a variation of greedy algorithms in which the algorithm is allowed to make modifications to previously colored vertices by...

Bousquet, Nicolas Heinrich, Marc

Let k and d be such that k ≥ d + 2. Consider two k-colourings of a d-degenerate graph G. Can we transform one into the other by recolouring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. However, Cereceda ...

Bousquet, Nicolas Heinrich, Marc

Let k and d be such that k ≥ d + 2. Consider two k-colourings of a d-degenerate graph G. Can we transform one into the other by recolouring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. However, Cereceda ...

Godin, Thibault

We prove, for various important classes of Mealy automata, that almost all generated groups have an element of infinite order. In certain cases, it also implies other results such as exponential growth.