12 papers
Fair Division of Graphs: Beyond Traceability
Nicolas Bousquet, Frank Connor, Agnès Totschnig +1
In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally al…
The local complexity of certifying parity
Nicolas Bousquet, Laurent Feuilloley, Jorge Valenzuela +1
In this paper, we consider the problem of locally certifying that the size of a network is even, or more generally, congruent to some fixed number. The parity property is one of th…
Complexity landscape for local certification
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
An impressive recent line of work has charted the complexity landscape of distributed graph algorithms. For many settings, it has been determined which time complexities exist, and…
Shallow brambles
Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet +2
A graph class has polynomial expansion if there is a polynomial function such that for every graph , each of the depth- minors of has ave…
A subquadratic certification scheme for P5-free graphs
Nicolas Bousquet, Sébastien Zeitoun
In local certification, vertices of a -vertex graph perform a local verification to check if a given property is satisfied by the graph. This verification is performed thanks to…
How local constraints influence network diameter and applications to LCL generalizations
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees…
Renaming in distributed certification
Nicolas Bousquet, Louis Esperet, Laurent Feuilloley +1
Local certification is the area of distributed network computing asking the following question: How to certify to the nodes of a network that a global property holds, if they are l…
A note on locating-dominating sets in twin-free graphs
Nicolas Bousquet, Quentin Chuet, Victor Falgas-Ravry +2
In this short note, we prove that every twin-free graph on vertices contains a locating-dominating set of size at most . This improves the earlier bou…
Global certification via perfect hashing
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide i…
Local certification of forbidden subgraphs
Nicolas Bousquet, Linda Cook, Laurent Feuilloley +2
Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph de…
A Note on the Complexity of Graph Recoloring
Nicolas Bousquet
We say that a graph is -mixing if it is possible to transform any -coloring into any other via a sequence of single vertex recolorings keeping a proper coloring all along. Ce…
Local certification of local properties: tight bounds, trade-offs and new parameters
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called c…