19 citations · 218 across the 100 of their papers we have counts for
123 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…
Fatness and Flatness
Arnold Filtser, Hung Le, Nikolas Mählmann +2
Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of s…
Induced Erdős--Pósa property for long holes, long thetas, and beyond
Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk +2
The induced Erdős--Pósa property in graphs relates the maximum number of pairwise anti-adjacent copies of an object with the minimum number of neighborhoods required to hit all cop…
Coarse Balanced Separators in Fat-Minor-Free Graphs
Édouard Bonnet, Hung Le, Marcin Pilipczuk +1
Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just b…
Pattern-Sparse Tree Decompositions in -Minor-Free Graphs
Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
Given an -minor-free graph and an integer , our main technical contribution is sampling in randomized polynomial time an induced subgraph of and a tree decomposi…
A Polynomial Coreset for Furthest Neighbor in Planar Metrics
Kacper Kluk, Hung Le, Wojciech Nadara +3
A furthest neighbor data structure on a metric space and a set answers the following query: given , output maximizing $\mathr…