Sokołowski, Marek
- Flipper games for monadically stable graph classes
2023/01/31 by Gajarský, Jakub, Mählmann, Nikolas, McCarty, Rose +6 · 9 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)
- Compact representation for matrices of bounded twin-width
2021/10/15 by Michał Pilipczuk, Pilipczuk, Michał, Marek Sokołowski +3 · 4 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
- Graphs of bounded twin-width are quasi-polynomially χ-bounded
2022/02/15 by Michał Pilipczuk, Marek Sokołowski, Pilipczuk, Michał +1 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.DM #math.CO
- Fully dynamic approximation schemes on planar and apex-minor-free graphs
2023/10/31 by Tuukka Korhonen, Wojciech Nadara, Korhonen, Tuukka +5 · 3 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
- Simpler and faster algorithms for detours in planar digraphs
2023/01/06 by Meike Hatzel, Konrad Majewski, Hatzel, Meike +5 · 2 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #VLSI and FPGA Design Techniques
- Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
2024/02/19 by Tuukka Korhonen, Korhonen, Tuukka, Marek Sokołowski +1 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #graph theory and CDMA systems
- Determining 4-edge-connected components in linear time
2021/05/04 by Wojciech Nadara, Nadara, Wojciech, Mateusz Radecki +5 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
- Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
2022/03/09 by Majewski, Konrad, Masařík, Tomáš, Novotná, Jana +4 · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
- Sparse Graphs of Twin-width 2 Have Bounded Tree-width
2023/07/04 by Bergougnoux, Benjamin, Gajarský, Jakub, Guśpiel, Grzegorz +3 · 1 citation
#05C75 #68R10 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
- Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
2023/07/01 by Kowalik, Łukasz, Lassota, Alexandra, Majewski, Konrad +2 · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences