291 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Centre National de la Recherche ScientifiqueFR223 papers
- Université de MontpellierFR184 papers
- Institut national de recherche en sciences et technologies du numériqueFR39 papers
- Université Montpellier 233 papers
- Data Management (Italy)IT24 papers
- Institut National Polytechnique de ToulouseFR24 papers
- Université Paul-Valéry MontpellierFR17 papers
- École Normale Supérieure de LyonFR16 papers
- Centre de Coopération Internationale en Recherche Agronomique pour le DéveloppementFR15 papers
- National and Kapodistrian University of AthensGR15 papers
- Lyon 1 UniversitéFR11 papers
- UMR Botanique et Modélisation de l’Architecture des Plantes et des végétationsFR11 papers
48 papers · 1 filter
Incremental computation of the set of period sets
Eric Rivals
Overlaps between words are crucial in many areas of computer science, such as code design, stringology, and bioinformatics. A self overlapping word is characterized by its periods…
Constrained Flows in Networks
Stéphane Bessy, Jørgen Bang-Jensen, Lucas Picasarri-Arrieta
The support of a flow in a network is the subdigraph induced by the arcs for which . We discuss a number of results on flows in networks where we put certain rest…
Contact graphs of boxes with unidirectional contacts
Daniel Gonçalves, Vincent Limouzy, Pascal Ochem
This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these gr…
Digraph redicolouring
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse +2
Given two -dicolourings of a digraph , we prove that it is PSPACE-complete to decide whether we can transform one into the other by recolouring one vertex at each step while…
Some Notes on Polyadic Concept Analysis
Alexandre Bazin, Giacomo Kahn, Camille Noûs
Despite the popularity of Formal Concept Analysis (FCA) as a mathematical framework for data analysis, some of its extensions are still considered arcane. Polyadic Concept Analysis…
Edge Degeneracy: Algorithmic and Structural Results
Stratis Limnios, Christophe Paul, Joanny Perret +1
We consider a cops and robber game where the cops are blocking edges of a graph, while the robber occupies its vertices. At each round of the game, the cops choose some set of edge…
Exact square coloring of subcubic planar graphs
Florent Foucaud, Hervé Hocquard, Suchismita Mishra +4
We study the exact square chromatic number of subcubic planar graphs. An exact square coloring of a graph G is a vertex-coloring in which any two vertices at distance exactly 2 rec…
Graphs with the second and third maximum Wiener index over the 2-vertex connected graphs
Stéphane Bessy, François Dross, Martin Knor +1
Wiener index, defined as the sum of distances between all unordered pairs of vertices, is one of the most popular molecular descriptors. It is well known that among 2-vertex connec…
Repetition avoidance in products of factors
Pamela Fleischmann, Pascal Ochem, Kamellia Reshadi
We consider a variation on a classical avoidance problem from combinatorics on words that has been introduced by Mousavi and Shallit at DLT 2013. Let be the su…
Characterization of infinite LSP words and endomorphisms preserving the LSP property
Gwenaël Richomme
Answering a question of G. Fici, we give an -adic characterization of thefamily of infinite LSP words, that is, the family of infinite words having all their left special factor…
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
Julien Destombes, Andrei Romashchenko
We suggest necessary conditions of soficness of multidimensional shifts formulated in termsof resource-bounded Kolmogorov complexity. Using this technique we provide examples ofeff…
Quasiperiods of biinfinite Sturmian words
Florian Barbero, Guilhem Gamard, Anaël Grandjean
We study the notion of quasiperiodicity, in the sense of "coverability", for biinfinite words. All previous work about quasiperiodicity focused on right infinite words, but the pas…
Discrete Morse theory for the collapsibility of supremum sections
Balthazar Bauer, Lucas Isenmann
The Dushnik-Miller dimension of a poset is the minimal number of linear extensions of such that is the intersection of $\le_1, \ldots…
The expressiveness of quasiperiodic and minimal shifts of finite type
Bruno Durand, Andrei Romashchenko
We study multidimensional minimal and quasiperiodic shifts of finite type. We prove for these classes several results that were previously known for the shifts of finite type in ge…
Out-colourings of Digraphs
Noga Alon, Joergen Bang-Jensen, Stéphane Bessy
We study vertex colourings of digraphs so that no out-neighbourhood is monochromatic and call such a colouring an {\bf out-colouring}. The problem of deciding whether a given digra…
On some interesting ternary formulas
Pascal Ochem, Matthieu Rosenfeld
We obtain the following results about the avoidance of ternary formulas. Up to renaming of the letters, the only infinite ternary words avoiding the formula (…
A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
François Dross, Mickael Montassier, Alexandre Pinlou
We prove that every triangle-free planar graph of order and size has an induced linear forest with at least vertices, and thus at least $\frac{5n + 8}{…
The Geodetic Hull Number is Hard for Chordal Graphs
Stéphane Bessy, Mitre C. Dourado, Lucia D. Penso +1
We show the hardness of the geodetic hull number for chordal graphs.
2-subcoloring is NP-complete for planar comparability graphs
Pascal Ochem
A -subcoloring of a graph is a partition of the vertex set into at most cluster graphs, that is, graphs with no induced . 2-subcoloring is known to be NP-complete for c…
On repetition thresholds of caterpillars and trees of bounded degree
Borut Lužar, Pascal Ochem, Alexandre Pinlou
The repetition threshold is the smallest real number such that there exists an infinite word over a -letter alphabet that avoids repetition of exponent strictly greater than…
Avoidability of circular formulas
Guilhem Gamard, Pascal Ochem, Gwenaël Richomme +1
Clark has defined the notion of -avoidance basis which contains the avoidable formulas with at most variables that are closest to be unavoidable in some sense. The family $C…
Avoidability of formulas with two variables
Pascal Ochem, Matthieu Rosenfeld
In combinatorics on words, a word over an alphabet is said to avoid a pattern over an alphabet of variables if there is no factor of such that wher…
Hitting minors, subdivisions, and immersions in tournaments
Jean-Florent Raymond
The Erdős-Pósa property relates parameters of covering and packing of combinatorial structures and has been mostly studied in the setting of undirected graphs. In this note, we use…
Periodicity in Rectangular Arrays
Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit +1
We discuss several two-dimensional generalizations of the familiar Lyndon-Schutzenberger periodicity theorem for words. We consider the notion of primitive array (as one that canno…