6 papers
Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity
Édouard Bonnet, Julien Duron, Marcin Pilipczuk +2
The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excludin…
QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík +2
We present a quasipolynomial-time approximation scheme (QPTAS) for the Maximum Independent Set (\textsc{MWIS}) in graphs with a bounded number of pairwise vertex-disjoint and non-a…
Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
Édouard Bonnet, Colin Geniet, Eun Jung Kim +1
A signed tree model of a graph is a compact binary structure consisting of a rooted binary tree whose leaves are bijectively mapped to the vertices of , together with 2-colo…
Separability Properties of Monadically Dependent Graph Classes
Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis +5
A graph class is monadically dependent if one cannot interpret all graphs in colored graphs from using a fixed first-order interpretation. We prove that m…
Induced Minors and Region Intersection Graphs
Édouard Bonnet, Robert Hickingbotham
We show that for any positive integers and , there is a -induced-minor-free graph of girth at least that is not a region intersection graph over the class o…
Answering Related Questions
Édouard Bonnet
We introduce the meta-problem Sidestep for a problem , a metric over its inputs, and a map .…