Marek Sokolowski

According to our database, Marek Sokolowski authored at least 18 papers between 2021 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument.

Konrad Majewski, Tomás Masarík, Jana Masaríková, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski

ACM Trans. Comput. Theory, 2024

Half-integral Erdös-Pósa property for non-null <i>S</i>-<i>T</i> paths.

Vera Chekan, Colin Geniet, Meike Hatzel, Michal Pilipczuk, Marek Sokolowski, Michal T. Seweryn, Marcin Witkowski

CoRR, 2024

Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth.

Tuukka Korhonen, Marek Sokolowski

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard.

Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michal Pilipczuk, Marek Sokolowski

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Fully dynamic approximation schemes on planar and apex-minor-free graphs.

Tuukka Korhonen, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Exact Shortest Paths with Rational Weights on the Word RAM.

Adam Karczmarz, Wojciech Nadara, Marek Sokolowski

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Elementary first-order model checking for sparse graphs.

Jakub Gajarský, Michal Pilipczuk, Marek Sokolowski, Giannos Stamoulis, Szymon Torunczyk

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

2023

Graphs of bounded twin-width are quasi-polynomially <i>χ</i>-bounded.

Michal Pilipczuk, Marek Sokolowski

J. Comb. Theory B, July, 2023

Bounds on Half Graph Orders in Powers of Sparse Graphs.

Marek Sokolowski

Electron. J. Comb., 2023

Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number.

Konrad Majewski, Michal Pilipczuk, Marek Sokolowski

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Simpler and faster algorithms for detours in planar digraphs.

Meike Hatzel, Konrad Majewski, Michal Pilipczuk, Marek Sokolowski

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width.

Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guspiel, Petr Hlinený, Filip Pokrývka, Marek Sokolowski

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

Flipper Games for Monadically Stable Graph Classes.

Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michal Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokolowski, Szymon Torunczyk

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Dynamic treewidth.

Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Graphs of bounded twin-width are quasi-polynomially χ-bounded.

Michal Pilipczuk, Marek Sokolowski

CoRR, 2022

Compact Representation for Matrices of Bounded Twin-Width.

Michal Pilipczuk, Marek Sokolowski, Anna Zych-Pawlewicz

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

2021

Maintaining CMSO₂ properties on dynamic structures with bounded feedback vertex number.

Konrad Majewski, Michal Pilipczuk, Marek Sokolowski

CoRR, 2021

Determining 4-Edge-Connected Components in Linear Time.

Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz, Marek Sokolowski

Proceedings of the 29th Annual European Symposium on Algorithms, 2021