Home » Publications
See also my DBLP page.
2024
-
T. Korhonen, M. Sokołowski
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
accepted to STOC 2024, full paper on arXiV [link] -
A. Karczmarz, W. Nadara, M. Sokołowski
Exact Shortest Paths with Rational Weights on the Word RAM
SODA 2024, full paper on arXiV [link] -
T. Korhonen, W. Nadara, Mi. Pilipczuk, M. Sokołowski
Fully Dynamic Approximation Schemes on Planar and Apex-Minor-Free Graphs
SODA 2024, full paper on arXiV [link] -
Ł. Kowalik, A. Lassota, K. Majewski, Mi. Pilipczuk, M. Sokołowski
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
SOSA 2024, also on arXiV [link] -
J. Gajarský, Mi. Pilipczuk, Sz. Toruńczyk, G. Stamoulis, M. Sokołowski
Elementary first-order model checking for sparse graphs
under submission, full paper on arXiV [link]
2023
-
T. Korhonen, K. Majewski, W. Nadara, Mi. Pilipczuk, M. Sokołowski
Dynamic Treewidth
FOCS 2023 [link], full paper on arXiV [link] -
Mi. Pilipczuk, M. Sokołowski
Graphs of bounded twin-width are quasi-polynomially chi-bounded
Journal of Combinatorial Theory, Series B [link], available on arXiV [link] -
K. Majewski, Mi. Pilipczuk, M. Sokołowski
Maintaining CMSO2 properties on dynamic structures with bounded feedback vertex number
STACS 2023 [link], full paper on arXiV [link] -
M. Hatzel, K. Majewski, Mi. Pilipczuk, M. Sokołowski
Simpler and faster algorithms for detours in planar digraphs
SOSA 2023 [link], also on arXiV [link] -
J. Gajarský, N. Mählmann, R. McCarty, P. Ohlmann, Mi. Pilipczuk, W. Przybyszewski, S. Siebertz, M. Sokołowski, Sz. Toruńczyk
Flipper games for monadically stable graph classes
ICALP 2023 [link], full paper on arXiV [link] -
B. Bergougnoux, J. Gajarský, G. Guśpiel, P. Hlinený, F. Pokrývka, M. Sokołowski
Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width
ISAAC 2023 [link], also on arXiV [link] -
M. Sokołowski
Bounds on Half Graph Orders in Powers of Sparse Graphs
Electronic Journal of Combinatorics [link], extended abstract at EUROCOMB 2021 [link (paywall)], full paper on arXiV [link]
2022
-
K. Majewski, T. Masarík, J. Novotná, K. Okrasa, Ma. Pilipczuk, P. Rzążewski, M. Sokołowski
Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument
ICALP 2022 [link], available on arXiV [link] -
Mi. Pilipczuk, M. Sokołowski, A. Zych-Pawlewicz
Compact Representation for Matrices of Bounded Twin-Width
STACS 2022 [link], full paper on arXiV [link]