1 citations · 4 across the 22 of their papers we have counts for
4 papers · 1 filter
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…
Determining 4-edge-connected components in linear time
Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz +1
In this work, we present the first linear time deterministic algorithm computing the 4-edge-connected components of an undirected graph. First, we show an algorithm listing all 3-e…
Bounds on half graph orders in powers of sparse graphs
Marek Sokołowski
Half graphs and their variants, such as ladders, semi-ladders and co-matchings, are combinatorial objects that encode total orders in graphs. Works by Adler and Adler (Eur. J. Comb…