Marek Sokolowski

41 papers A* 9A 3B 2Journal 25Unranked 2
YearRankTypeTitle / Venue / Authors
2026 J jnl
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions.
CoRR
Sang-il Oum, Marek Sokolowski
2026 A* conf
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP.
SODA
Adam Karczmarz, Wojciech Nadara, Marek Sokolowski
2025 A* conf
Fully Dynamic Biconnectivity in Õ(log² n) Time.
STOC
Jacob Holm, Wojciech Nadara, Eva Rotenberg, Marek Sokolowski
2025 J jnl
Fully dynamic biconnectivity in Õ(log² n) time.
CoRR
Jacob Holm, Wojciech Nadara, Eva Rotenberg, Marek Sokolowski
2025 J jnl
Low rank MSO.
CoRR
Mikolaj Bojanczyk, Michal Pilipczuk, Wojciech Przybyszewski, Marek Sokolowski, Giannos Stamoulis
2025 J jnl
Maintaining CMSO
ACM Trans. Comput. Theory
Konrad Majewski, Michal Pilipczuk, Marek Sokolowski
2025 J jnl
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP.
CoRR
Adam Karczmarz, Wojciech Nadara, Marek Sokolowski
2025 B conf
Treedepth Inapproximability and Exponential ETH Lower Bound.
IPEC
Édouard Bonnet, Daniel Neuen, Marek Sokolowski
2025 J jnl
Treedepth Inapproximability and Exponential ETH Lower Bound.
CoRR
Édouard Bonnet, Daniel Neuen, Marek Sokolowski
2024 A* conf
Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth.
STOC
Tuukka Korhonen, Marek Sokolowski
2024 J jnl
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth.
CoRR
Tuukka Korhonen, Marek Sokolowski
2024 — conf
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard.
SOSA
Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michal Pilipczuk, Marek Sokolowski
2024 A* conf
Elementary first-order model checking for sparse graphs.
LICS
Jakub Gajarský, Michal Pilipczuk, Marek Sokolowski, Giannos Stamoulis, Szymon Torunczyk
2024 J jnl
Elementary first-order model checking for sparse graphs.
CoRR
Jakub Gajarský, Michal Pilipczuk, Marek Sokolowski, Giannos Stamoulis, Szymon Torunczyk
2024 A* conf
Exact Shortest Paths with Rational Weights on the Word RAM.
SODA
Adam Karczmarz, Wojciech Nadara, Marek Sokolowski
2024 A* conf
Fully dynamic approximation schemes on planar and apex-minor-free graphs.
SODA
Tuukka Korhonen, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski
2024 J jnl
Half-integral Erdös-Pósa property for non-null
CoRR
Vera Chekan, Colin Geniet, Meike Hatzel, Michal Pilipczuk, Marek Sokolowski, Michal T. Seweryn, Marcin Witkowski
2024 J jnl
Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument.
ACM Trans. Comput. Theory
Konrad Majewski, Tomás Masarík, Jana Masaríková, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski
2023 J jnl
Bounds on Half Graph Orders in Powers of Sparse Graphs.
Electron. J. Comb.
Marek Sokolowski
2023 J jnl
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard.
CoRR
Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michal Pilipczuk, Marek Sokolowski
2023 A* conf
Dynamic treewidth.
FOCS
Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski
2023 J jnl
Dynamic treewidth.
CoRR
Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski
2023 J jnl
Exact Shortest Paths with Rational Weights on the Word RAM.
CoRR
Adam Karczmarz, Wojciech Nadara, Marek Sokolowski
2023 A* conf
Flipper Games for Monadically Stable Graph Classes.
ICALP
Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michal Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokolowski, Szymon Torunczyk
2023 J jnl
Flipper games for monadically stable graph classes.
CoRR
Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michal Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokolowski, Szymon Torunczyk
2023 J jnl
Fully dynamic approximation schemes on planar and apex-minor-free graphs.
CoRR
Tuukka Korhonen, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski
2023 J jnl
Graphs of bounded twin-width are quasi-polynomially
J. Comb. Theory B
Michal Pilipczuk, Marek Sokolowski
2023 A conf
Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number.
STACS
Konrad Majewski, Michal Pilipczuk, Marek Sokolowski
2023 — conf
Simpler and faster algorithms for detours in planar digraphs.
SOSA
Meike Hatzel, Konrad Majewski, Michal Pilipczuk, Marek Sokolowski
2023 J jnl
Simpler and faster algorithms for detours in planar digraphs.
CoRR
Meike Hatzel, Konrad Majewski, Michal Pilipczuk, Marek Sokolowski
2023 B conf
Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width.
ISAAC
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guspiel, Petr Hlinený, Filip Pokrývka, Marek Sokolowski
2023 J jnl
Sparse Graphs of Twin-width 2 Have Bounded Tree-width.
CoRR
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guspiel, Petr Hlinený, Filip Pokrývka, Marek Sokolowski
2022 A conf
Compact Representation for Matrices of Bounded Twin-Width.
STACS
Michal Pilipczuk, Marek Sokolowski, Anna Zych-Pawlewicz
2022 J jnl
Graphs of bounded twin-width are quasi-polynomially χ-bounded.
CoRR
Michal Pilipczuk, Marek Sokolowski
2022 A* conf
Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument.
ICALP
Konrad Majewski, Tomás Masarík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski
2022 J jnl
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument.
CoRR
Konrad Majewski, Tomás Masarík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski
2021 J jnl
Bounds on half graph orders in powers of sparse graphs.
CoRR
Marek Sokolowski
2021 J jnl
Compact representation for matrices of bounded twin-width.
CoRR
Michal Pilipczuk, Marek Sokolowski, Anna Zych-Pawlewicz
2021 A conf
Determining 4-Edge-Connected Components in Linear Time.
ESA
Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz, Marek Sokolowski
2021 J jnl
Determining 4-edge-connected components in linear time.
CoRR
Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz, Marek Sokolowski
2021 J jnl
Maintaining CMSO
CoRR
Konrad Majewski, Michal Pilipczuk, Marek Sokolowski