From the 1 of 7 linked papers with an AI index.
7 papers
Adjacency labelling for proper minor-closed graph classes
Vida DujmoviÄ, Cyril Gavoille, Gwenaël Joret +3
The paper proves that every proper minor‑closed class of graphs admits an adjacency labeling scheme using (1+o(1))·log₂ n bits, equivalently showing the existence of an n^{1+o(1)}‑…
Entanglement from Expansion: High Rank-Width in Deterministic Graphs
Tristan Cam, Cyril Gavoille, Yvan Le Borgne +1
Entanglement in quantum graph states is intrinsically linked to rank-width, a graph complexity measure introduced by Oum and Seymour. In this work, we enable the preparation of max…
Lower Bounds for Induced-Universal Graphs
Cyril Gavoille, Amaury Jacques
We give a series of new lower bounds on the minimum number of vertices required by a graph to contain every graph of a given family as induced subgraph. In particular, we show that…
An Improved Bound for Plane Covering Paths
Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz +8
A covering path for a finite set of points in the plane is a polygonal path such that every point of lies on a segment of the path. The vertices of the path need not be at…
Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
Marthe Bonamy, Cyril Gavoille, Timothé Picavet +1
We give a new, short proof that graphs embeddable in a given Euler genus- surface admit a simple -round -approximation distributed algorithm for Minimum Dominating Set…
Isometric-Universal Graphs for Trees
Edgar Baucher, François Dross, Cyril Gavoille
We consider the problem of finding the smallest graph that contains two input trees each with at most vertices preserving their distances. In other words, we look for an isomet…