7 papers
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…
Adjacency labelling for proper minor-closed graph classes
Vida Dujmović, Cyril Gavoille, Gwenaël Joret +3
We show that every proper minor-closed class of graphs admits a -bit adjacency labelling scheme. Equivalently, for every proper minor-closed class a…
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…
Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
Marthe Bonamy, Cyril Gavoille, Timothé Picavet +1
We show that graphs excluding as a minor admit a -round -approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Min…