3 citations · 4 across the 6 of their papers we have counts for
7 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…
Hereditary 2-WQO Graph Classes Have Bounded Clique-Width
Julien Duron, Nikolas Mählmann, Szymon Toruńczyk
A graph class is -WQO if its -labeled graphs are well-quasi-ordered under label-preserving induced subgraph embeddings. We show that every hereditary graph class that is -…
Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, Rose McCarty +2
Monadic dependence is a proposed structural dividing line for fixed-parameter tractability of first-order model checking on hereditary graph classes. A graph class is \emph{monadic…
Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
A conjecture in algorithmic model theory predicts that the model-checking problem for first-order logic is fixed-parameter tractable on a hereditary graph class if and only if the…
Elementary first-order model checking for sparse graphs
Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski +2
It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, S…
First-Order Model Checking on Monadically Stable Graph Classes
Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann +3
A graph class is called monadically stable if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from . We prove…
Flip-width: Cops and Robber on dense graphs
Szymon Toruńczyk
We define new graph parameters, called flip-width, that generalize treewidth, degeneracy, and generalized coloring numbers for sparse graphs, and clique-width and twin-width for de…