Publications

Marcin Wrochna

Number of publications: 40

2023

• Piotr Wygocki , M Ulfig, Marcin Wrochna , A Zapała, M Zieleń, U Sankowska, K Zieliński, N Gajewska, Piotr Sankowski , Damian Drzyzga, P-674 Automatizing ovarian follicle counting and measurement with artificial intelligence, HUMAN REPRODUCTION, 39th Annual Meeting of the European Society of Human Reproduction and Embryology, Copenhagen, Denmark, 25 June 2023 - 28 June 2023, 38 (Supplement_1) 2023, p. i507. See in PBN
• Miguel Romero, Marcin Wrochna , Stanislav Živný, Pliability and Approximating Max-CSPs, Journal of the ACM, 70 (6) 2023, p. 1-43. See in PBN
• Andrei Krokhin, Jakub Opršal, Marcin Wrochna , Stanislav Živný, Topology and Adjunction in Promise Constraint Satisfaction, SIAM Journal on Computing, 52 (1) 2023, p. 38-79. See in PBN

2022

• Balázs F. Mezei, Stanislav Živný, Marcin Wrochna , PTAS for Sparse General-Valued CSPs, ACM Transactions on Algorithms, 2022. See in PBN

2021

• Archontia Giannopoulou, Michał Pilipczuk , Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna , Linear kernels for edge deletion problems to immersion-closed graph classes, SIAM Journal on Discrete Mathematics, 35 (1) 2021, p. 105-151. See in PBN
• Balazs F. Mezei, Marcin Wrochna , Stanislav Zivny, PTAS for Sparse General-Valued CSPs, 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Rome, Italy, 29 June 2021 - 2 July 2021. See in PBN
• Alex Brandts, Marcin Wrochna , Stanislav Živný, The Complexity of Promise SAT on Non-Boolean Domains, ACM Transactions on Computation Theory, 13 (4) 2021, p. 1-20. See in PBN
• Miguel Romero, Marcin Wrochna , Stanislav Živný, Treewidth-pliability and PTAS for Max-CSPS, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN

2020

• Marcin Wrochna , Homomorphism Reconfiguration via Homotopy, SIAM Journal on Discrete Mathematics, 34 (1) 2020, p. 328-350. See in PBN
• Marcin Wrochna , Stanislav Živný, Improved hardness for H-colourings of G-colourable graphs, 31st ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, the United States of America, 5 January 2020 - 8 January 2020. See in PBN
• Marcin Wrochna , PACE solver description: Sallow: A heuristic algorithm for treedepth decompositions, Leibniz International Proceedings in Informatics, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), Hong Kong, China, 14 December 2020 - 18 December 2020. See in PBN
• Alex Brandts, Marcin Wrochna , Stanislav Zivny, The complexity of promise SAT on non-boolean domains, Leibniz International Proceedings in Informatics, 47th International Colloquium on Automata, Languages, and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020. See in PBN
• Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna , Stanislav Živný, The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems, SIAM Journal on Computing, 49 (6) 2020, p. 1232-1248. See in PBN
• Dusan Knop, Michał Pilipczuk , Marcin Wrochna , Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints, ACM Transactions on Computation Theory, 12 (3) 2020, p. 19:1--19:19. See in PBN

2019

• Archontia C. Giannopoulou, Michał Pilipczuk , Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna , Cutwidth: Obstructions and Algorithmic Aspects, Algorithmica, 81 (2) 2019, p. 557-588. See in PBN
• Marcin Pilipczuk , Michał Pilipczuk , Marcin Wrochna , Edge Bipartization Faster than 2^k, Algorithmica, 81 (3) 2019, p. 917–966. See in PBN
• Claude Tardif, Marcin Wrochna , Hedetniemi's conjecture and strongly multiplicative graphs, SIAM Journal on Discrete Mathematics, 33 (4) 2019, p. 2218-2250. See in PBN
• Eduard Eiben, Robert Ganian, Dušan Knop, Sebastian Ordyniak, Michał Pilipczuk , Marcin Wrochna , Integer Programming and Incidence Treedepth, 20th Conference on Integer Programming and Combinatorial Optimization, Ann Arbor, the United States of America, 22 May 2019 - 24 May 2019. See in PBN
• Marcin Wrochna , On inverse powers of graphs and topological implications of Hedetniemi's conjecture, Journal of Combinatorial Theory. Series B, 139 2019, p. 267-295. See in PBN
• Daniel Král', Taísa L. Martins, Péter Pál Pach, Marcin Wrochna , The step Sidorenko property and non-norming edge-transitive graphs, Journal of Combinatorial Theory - Series A, 162 2019, p. 34-54. See in PBN
• Dušan Knop, Michał Pilipczuk , Marcin Wrochna , Tight complexity lower bounds for integer linear programming with few constraints, Leibniz International Proceedings in Informatics, 36th International Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, 13 March 2019 - 16 March 2019, 126 2019, p. 44:1--44:15. See in PBN
• Marthe Bonamy, Łukasz Kowalik , Michał Pilipczuk , Arkadiusz Socała, Marcin Wrochna , Tight Lower Bounds for the Complexity of Multicoloring, ACM Transactions on Computation Theory, 11 (3) 2019, p. 1-19. See in PBN
• Bart M. P. Jansen, Marcin Pilipczuk , Marcin Wrochna , Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor, Algorithmica, 81 (10) 2019, p. 3936-3967. See in PBN

2018

• Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michał Pilipczuk , Marcin Wrochna , Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth, ACM Transactions on Algorithms, 14 (3) 2018, p. 1–45. See in PBN
• Marthe Bonamy, Łukasz Kowalik , Jesper Nederlof, Michał Pilipczuk , Arkadiusz Socała, Marcin Wrochna , On Directed Feedback Vertex Set Parameterized by Treewidth, 44th International Workshop on Graph-Theoretic Concepts in Computer, Cottbus, Germany, 27 June 2018 - 29 June 2018. See in PBN
• Michał Pilipczuk , Marcin Wrochna , On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs, ACM Transactions on Computation Theory, 9 (4) 2018, p. 18: 1–36. See in PBN
• Bart M. P. Jansen, Marcin Pilipczuk , Marcin Wrochna , Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor, 12th International Symposium on Parameterized and Exact Computation, Vienna, Austria, 6 September 2017 - 8 September 2017. See in PBN

2017

• Archontia Giannopoulou, Michał Pilipczuk , Jean-florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna , Cutwidth: Obstructions and Algorithmic Aspects, 11th International Symposium on Parameterized and Exact Computation, Aarhus, Denmark, 24 August 2016 - 26 August 2016. See in PBN
• Marcin Pilipczuk , Michał Pilipczuk , Marcin Wrochna , Edge Bipartization Faster Than 2 k∗, 11th International Symposium on Parameterized and Exact Computation, Aarhus, Denmark, 24 August 2016 - 26 August 2016, 63 2017, p. 26:1--26:13. See in PBN
• Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk , Saket Saurabh, Marcin Wrochna , Fully polynomial-time parameterized computations for graphs and matrices of low treewidth, 28th ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16 January 2017 - 19 January 2017. See in PBN
• Archontia Giannopoulou, Michał Pilipczuk , Jean-florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna , Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
• Marcin Wrochna , Reconfiguration in bounded bandwidth and tree-depth, Journal of Computer and System Sciences, 93 2017, p. 1-10. See in PBN
• Marthe Bonamy, Łukasz Kowalik , Michał Pilipczuk , Arkadiusz Socała, Marcin Wrochna , Tight Lower Bounds for the Complexity of Multicoloring, 25th Annual European Symposium on Algorithms, Vienna, Austria, 4 September 2017 - 6 September 2017, 87 2017, p. 18:1--18:14. See in PBN

2016

• Michał Pilipczuk , Marcin Wrochna , On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orlean, France, 17 February 2016 - 20 February 2016. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Marcin Wrochna , Erik Jan van Leeuwen, Polynomial Kernelization for Removing Induced Claws and Diamonds, Theory of Computing Systems, 2016. See in PBN
• Marek Cygan , Erik Jan van Leeuwen, Marcin Pilipczuk , Michał Pilipczuk , Marcin Wrochna , Polynomial Kernelization for Removing Induced Claws and Diamonds, 41st International Workshop on Graph-Theoretic Concepts in Computer Science, Garching, Germany, 17 June 2015 - 19 June 2015. See in PBN
• Marcin Wrochna , Square-free graphs are multiplicative, Journal of Combinatorial Theory. Series B, 122 2016, p. 479-507. See in PBN

2015

• Marcin Wrochna , Homomorphism Reconfiguration via Homotopy, 32nd International Symposium on Theoretical Aspects of Computer Science, Garching, Germany, 4 March 2015 - 7 March 2015. See in PBN

2014

• Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Marcin Wrochna , Reconfiguration over Tree Decompositions, 9th International Symposium on Parameterized and Exact Computation, Wrocław, Poland, 10 September 2014 - 12 September 2014. See in PBN
• Paul S. Bonsma, Marcin Kamiński, Marcin Wrochna , Reconfiguring Independent Sets in Claw-Free Graphs, 14th Scandinavian Symposium and Workshops on Algorithm Theory, Kopenhaga, Denmark, 2 July 2014 - 4 July 2014. See in PBN