3 citations · 5 across the 5 of their papers we have counts for
7 papers
Reduction ratio of the IS-algorithm: worst and random cases
Vincent Jugé
We study the IS-algorithm, a well-known linear-time algorithm for computing the suffix array of a word. This algorithm relies on transforming the input word into another word,…
Galloping in fast-growth natural merge sorts
Elahe Ghasemi, Vincent Jugé, Ghazal Khalighinejad +1
We study the impact of merging routines in merge-based sorting algorithms. More precisely, we focus on the galloping routine that TimSort uses to merge monotonic sub-arrays, hereaf…
Uniform generation of infinite concurrent runs: the case of trace monoids
Samy Abbes, Vincent Jugé
We introduce an algorithm for the uniform generation of infinite runs in concurrent systems under a partial order probabilistic semantics. We work with trace monoids as concurrency…
Counting bi-colored A'Campo forests
Noémie Combe, Vincent Jugé
We give an efficient method of counting bi-colored A'Campo forests and provide a stratification criterion for the space of those graphs. We deduce an algorithm to count these fores…
Abelian Ramsey Length and Asymptotic Lower Bounds
Vincent Jugé
This technical note aims at evaluating an asymptotic lower bound on abelian Ramsey lengths.
Uniform measures on braid monoids and dual braid monoids
Samy Abbes, Sébastien Gouëzel, Vincent Jugé +1
We aim at studying the asymptotic properties of typical positive braids, respectively positive dual braids. Denoting by the uniform distribution on positive (dual) braids of…
Curve Diagrams, Laminations, and the Geometric Complexity of Braids
Vincent Jugé
Braids can be represented geometrically as curve diagrams. The geometric complexity of a braid is the minimal complexity of a curve diagram representing it. We introduce and study…