6 papers
Leader Election via Unique Sink Orientation
Jérémie Chalopin, Maria Kokkou
A Locally Checkable Labeling (LCL) is a distributed constraint satisfaction problem defined on a bounded-degree graph that relates a finite set of input labels to a finite set of o…
Generating minimal redundant and maximal irredundant sets in incidence graphs
Emanuel Castelo, Jérémie Chalopin, Oscar Defrain +1
It has been proved by Boros and Makino that there is no output-polynomial-time algorithm enumerating the minimal redundant sets or the maximal irredundant sets of a hypergraph, unl…
Distance-based certification for leader election in meshed graphs and local recognition of their subclasses
Jérémie Chalopin, Victor Chepoi, Maria Kokkou
In this paper, we present a 2-local proof labeling scheme with labels in for leader election in anonymous meshed graphs. Meshed graphs form a general class of graphs d…
Boundary rigidity of systolic and Helly complexes
MartÃn Blufstein, Jérémie Chalopin, Victor Chepoi
In this article, we prove that finite (weakly) systolic and Helly complexes can be reconstructed from their boundary distances (computed in their 1-skeleta). Furthermore, Helly com…
On -unimodality of radius functions in graphs: structure and algorithms
Jérémie Chalopin, Victor Chepoi, Feodor Dragan +2
For every weight assignment to the vertices in a graph , the radius function maps every vertex of to its largest weighted distance to the other vertices. The cen…
Geometry of convex geometries
Jérémie Chalopin, Victor Chepoi, Kolja Knauer
We prove that any convex geometry on points and any ideal of can be realized as the intersection pat…