948 citations
- Centre National de la Recherche ScientifiqueFR158 papers
- Pôle de recherche et d'enseignement supérieur Université Paris-EstFR126 papers
- Université Paris-Est CréteilFR121 papers
- Université Paris CitéFR52 papers
- Laboratoire d'Informatique Gaspard-MongeFR50 papers
- École nationale des ponts et chausséesFR40 papers
- Laboratoire Interuniversitaire des Systèmes AtmosphériquesFR31 papers
- Laboratoire Techniques, Territoires et SociétésFR29 papers
- Laboratoire d’Analyse et de Mathématiques AppliquéesFR27 papers
- Université Paris-SaclayFR26 papers
- CERMICSFR25 papers
- Institut national de recherche en sciences et technologies du numériqueFR23 papers
10 papers · 1 filter
Algorithmic and algebraic aspects of unshuffling permutations
Samuele Giraudo, Stéphane Vialette
A permutation is said to be a square if it can be obtained by shuffling two order-isomorphic patterns. The definition is intended to be the natural counterpart to the ordinary shuf…
Decomposing Cubic Graphs into Connected Subgraphs of Size Three
Laurent Bulteau, Guillaume Fertin, Anthony Labarre +2
Let be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph into graphs taken from any non-empty $S'\subs…
Pattern matching in -avoiding permutations
Both Emerite Neou, Romeo Rizzi, Stéphane Vialette
Given permutations and with , the \emph{pattern matching} problem is to decide whether matches as an order-isomorphic subsequence. We give a line…
Hyper Temporal Networks
Carlo Comin, Roberto Posenato, Romeo Rizzi
Simple Temporal Networks (STNs) provide a powerful and general tool for representing conjunctions of maximum delay constraints over ordered pairs of temporal variables. In this pap…
Covering Problems for Partial Words and for Indeterminate Strings
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka +3
We consider the problem of computing a shortest solid cover of an indeterminate string. An indeterminate string may contain non-solid symbols, each of which specifies a subset of t…
A Note on the Longest Common Compatible Prefix Problem for Partial Words
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka +6
For a partial word the longest common compatible prefix of two positions , denoted , is the largest such that , where $\uparr…