Julien Duron

collaborators

2 papers

cs.CC2025

Mim-Width is paraNP-complete

Benjamin Bergougnoux, Édouard Bonnet, Julien Duron

We show that it is NP-hard to distinguish graphs of linear mim-width at most 1211 from graphs of sim-width at least 1216. This implies that Mim-Width, Sim-Width, One-Sided Mim-Widt…

math.CO2024

Adjacency Labeling Schemes for Small Classes

Édouard Bonnet, Julien Duron, John Sylvester +1

A graph class admits an implicit representation if, for every positive integer $n$ , its $n$ -vertex graphs have a $O (lo g n)$ -bit (adjacency) labeling scheme, i.e., their vertices c…