12 citations · 71 across the 72 of their papers we have counts for
8 papers · 1 filter
Algorithms and data structures for first-order logic with connectivity under vertex failures
Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz +2
We introduce a new data structure for answering connectivity queries in undirected graphs subject to batched vertex failures. Precisely, given any graph G and integer k, we can in…
Compact representation for matrices of bounded twin-width
Michał Pilipczuk, Marek Sokołowski, Anna Zych-Pawlewicz
For every fixed , we design a data structure that represents a binary matrix that is -twin-ordered. The data structure occupies bits, whi…
Maintaining properties on dynamic structures with bounded feedback vertex number
Konrad Majewski, Michał Pilipczuk, Marek Sokołowski
Let be a sentence of (monadic second-order logic with quantification over edge subsets and counting modular predicates) over the signature of graphs. We prese…
Stable graphs of bounded twin-width
Jakub Gajarský, Michał Pilipczuk, Szymon Toruńczyk
We prove that every class of graphs that is monadically stable and has bounded twin-width can be transduced from some class with bounded sparse twin-width. This genera…
Isolation schemes for problems on decomposable graphs
Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis +1
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87] provides a self-reduction scheme that allows one to assume that a given instance of a problem has a unique…
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
Daniel Lokshtanov, Pranabendu Misra, Michal Pilipczuk +2
In the Disjoint Paths problem, the input is an undirected graph on vertices and a set of vertex pairs, , and the task is to find pairwise verte…