Mapa strony
Ostatnia aktualizacja:
December 11. 2024 22:29:27
Aktualności / News > List of papers

List of papers

Journal papers

  1. K. Junosza-Szaniawski, P. Rzążewski, On the Complexity of Exact Algorithm for L(2,1)-labeling of Graphs, Information Processing Letters 111, pp. 697-701, 2011 (DOI: 10.1016/j.ipl.2011.04.010)
  2. K. Junosza-Szaniawski, P. Rzążewski, On the number of 2-packings in a connected graph, Discrete Mathematics 312, pp. 3444–3450, 2012 (DOI: 10.1016/j.disc.2012.02.005)
  3. K. Junosza-Szaniawski, J. Kratochvil, M. Liedloff, P. Rossmanith, P. Rzążewski, Fast Exact Algorithm for L(2,1)-Labeling of Graphs, Theoretical Computer Science 505, pp. 42-54, 2013  (DOI: 10.1016/j.tcs.2012.06.037)
  4. K. Junosza-Szaniawski, J. Kratochvil, M. Liedloff, P. Rzążewski, Determining the L(2,1)-span in Polynomial Space, Discrete Applied Mathematics 161, pp. 2052-2061, 2013 (DOI: 10.1016/j.dam.2013.03.027)empty
  5. P. Rzążewski, Exact Algorithm for Graph Homomorphism and Locally Injective Graph Homomorphism, Information Processing Letters 114, pp. 387-391, 2014 (DOI: 10.1016/j.ipl.2014.02.012)
  6. K. Junosza-Szaniawski, P. Rzążewski, An Exact Algorithm for the Generalized List T-Coloring Problem, Discrete Mathematics and Theoretical Computer Science 16:3, pp. 77–94, 2014
  7. J.A. Bondy, Z. Lonc, P. Rzążewski, Constructing optimal k-radius sequences, SIAM J. Discrete Mathematics 30, pp. 452-464, 2016 (DOI: 10.1137/15M1023506)
    Erratum: J.A. Bondy, Z. Lonc, P. Rzążewski, Erratum: Constructing optimal k-radius sequences, SIAM J. Discrete Mathematics 31, pp. 645-646, 2017 (DOI: 10.1137/16M108505X)
  8. B. Bosek, S. Czerwiński, J. Grytczuk, P. Rzążewski, Harmonious coloring of uniform hypergraphs, Applicable Analysis and Discrete Mathematics 10, pp. 73-87, 2016 (DOI:  10.2298/AADM160411008B)
  9. K. Kaczmarski, P. Rzążewski, A. Wolant, Parallel algorithms constructing the cell graph, Concurrency and Computation: Practice and Experience 29, 2017 (DOI: 10.1002/cpe.3943)
  10. M. Dębski, Z. Lonc, P. Rzążewski, Achromatic and harmonious colorings of circulant graphs, Journal of Graph Theory 87, pp. 1097-1118, 2017 (DOI: 10.1002/jgt.22137)
  11. M. Dębski, Z. Lonc, P. Rzążewski, Sequences of radius k for complete bipartite graphs, Discrete Applied Mathematics 225, pp. 51--63, 2017 (DOI: 10.1016/j.dam.2017.03.017)
  12. M. Pergel, P. Rzążewski, On edge intersection graphs of paths with 2 bends, Discrete Applied Mathematics 226, pp. 106--116, 2017 (DOI: 10.1016/j.dam.2017.04.023)
  13. M. Dębski, Z. Lonc, P. Rzążewski, Harmonious and achromatic colorings of fragmentable hypergraphs, European Journal of Combinatorics, 66, pp. 60-80, 2017 (DOI: 10.1016/j.ejc.2017.06.013)
  14. Z. Lonc, P. Naroski, P. Rzążewski, Tight Euler tours in uniform hypergraphs - computational aspects, Discrete Mathematics and Theoretical Computer Science 19:3, #2, 2017
  15. É. Bonnet, T. Miltzow, P. Rzążewski, Complexity of token swapping and its vartiants, Algorithmica 80, pp. 2656--2682, 2018 (DOI: 10.1007/s00453-017-0387-0)
  16. V. Garnero, K. Junosza-Szaniawski, M. Liedloff, P. Montealegre, P. Rzążewski, Fixing improper colorings of graphs, Theoretical Computer Science 711C, pp. 66-78 2018 (DOI: 10.1016/j.tcs.2017.11.013)
  17. K. Junosza-Szaniawski, P. Rzążewski, J. Sokół, K. Węsek, Online coloring and L(2,1)-labeling of unit disk intersection graphs, SIAM J. Discrete Mathematics 32, pp. 1335-1350 (DOI: 10.1137/16M1097821)
  18. V.E. Brimkov, K. Junosza-Szaniawski, S. Kafer, J. Kratochvil, M. Pergel, P. Rzążewski, M. Szczepankiewicz, J. Terhaar, Homothetic Polygons and Beyond: Maximal Cliques in Intersection Graphs, Discrete Applied Mathematics 247, pp. 263-277, 2018 (DOI: 10.1016/j.dam.2018.03.046)
  19. Cs. Biró, É. Bonnet, D. Marx, T. Miltzow, P. Rzążewski, Fine-grained complexity of coloring unit disks and balls, Journal of Computational Geometry 9, pp. 47-80, 2018 (DOI: 10.20382/jocg.v9i2a4)
  20. E. Bonnet, P. Rzążewski, Optimality program in string and segment graphs, Algorithmica, 81(7), pp. 3047-3073,2019 (DOI: 10.1007/s00453-019-00568-7)
  21. D. Dereniowski, D. Osula, P. Rzążewski, Finding small-width connected path decompositions in polynomial time, Theoretical Computer Science 794, pp. 85-100, 2019
  22. C. Groenland, K. Okrasa, P. Rzążewski, A. Scott, P. Seymour, S. Spirkl, H-colouring Pt-free graphs in subexponential time, Discrete Applied Mathematics 267, pp. 184-189, 2019 (DOI: 10.1016/j.dam.2019.04.010)
  23. K. Junosza-Szaniawski, P. Rzążewski, J. Sokół, L(2,1)-labeling of disk intersection graphs, Discrete Applied Mathematics 227, pp. 71-81, 2020
  24. K. Edwards, P. Rzążewski, Complete colourings of hypergraphs, Discrete Mathematics 343, 111673 , 2020
  25. É. Bonnet, P. Rzążewski, F. Sikora, Designing RNA Secondary Structures is Hard, Journal of Computational Biology 27, pp. 302-316, 2020
  26. K. Okrasa, P. Rzążewski, Subexponential algorithms for variants of homomorphism problem in string graphs, Journal of Computer and System Sciences 109, pp. 126-144, 2020
  27. K. Dabrowski, C. Feghali, M. Johnson, G. Paesani, D. Paulusma, P. Rzążewski, On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest, Algorithmica, 2020
  28. J. Novotna, K. Okrasa, Mi. Pilipczuk, P. Rzążewski, E.J. van Leeuwen, B. Walczak, Subexponential-time algorithms for finding large induced sparse subgraphs, Algorithmica, 2020
  29. M. Bonamy, É. Bonnet, N. Bousquet, P. Charbit, P. Giannopoulos, E-J. Kim, P. Rzążewski, F. Sikora, S. Thomasse, EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs, Journal of the ACM 68, pp. 1-38, 2021
  30. K. Okrasa, P. Rzążewski, Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs, SIAM Journal on Computing 50(2), pp. 487-508, 2021
  31. M. Chudnovsky, J. King, Mi. Pilipczuk, P. Rzążewski, S. Spirkl, Finding large H-colorable subgraphs in hereditary graph classes, SIAM J. Discrete Math. 35(4), 2357-2386, 2021
  32. T. Masarik, I. Muzi, Ma. Pilipczuk, P. Rzążewski, M. Sorge, Packing Directed Cycles Quarter- and Half-Integrally, Combinatorica, 2022
  33. K. Junosza-Szaniawski, D. Nogalski, P. Rzążewski, Exact and approximation algorithms for sensor placement against DDoS attacks, International Journal of Applied Mathematics and Computer Science 31, pp. 35-49, 2022
  34. M. Bonamy, N. Bousquet, M. Pilipczuk, P. Rzążewski, S. Thomasse, B. Walczak, Degeneracy of P_t-free and C_{>= t}-free graphs with no large complete bipartite subgraphs, Journal of Combinatorial Theory, Series B 152, pp. 353-379, 2022
  35. M.G. Dobbins, L. Kleist, T. Milltzow, P. Rzążewski, ∀∃R-completeness and area-universality, Discrete and Computational Geometry 70, pp. 154-188 (2023)
  36. T. Masařík, M. Pilipczuk, P. Rzążewski, M. Sorge, Constant congestion brambles in directed graphs, SIAM J. Discrete Math. 36, pp. 922-938, 2022
  37. G. Paesani, D. Paulusma, P. Rzążewski, Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs, SIAM J. Discrete Math. 36, pp. 2453-2472, 2022
  38. M. Dębski, M. Piecyk, P. Rzążewski, Faster 3-coloring of small-diameter graph, SIAM J. Discrete Math. 36, pp. 2205-2224, 2022
  39. P. Dvořák, A.E. Feldmann, A. Rai, P. Rzążewski, Parameterized Inapproximability of Independent Sets in H-Free  Graphs, Algorithmica 85, pp. 902-928, 2023
  40. M. Krzyziński, P. Rzążewski, Sz. Tur, Coloring squares of planar graphs with small maximum degree, to appear in Discussiones Mathematicae Graph Theory, 2022
  41. M. Chudnovsky, S. Huang, P. Rzążewski, S. Spirkl, M. Zhong, Complexity of Ck-coloring in hereditary classes of graphs, Information and Computation 292, 105015, 2023
  42. H. Chen, B.M.P. Jansen, K. Okrasa, A. Pieterse, P. Rzążewski, Sparsification Lower Bounds for List-H-Coloring, ACM Transactions on Computation Theory 15, paper 8, p. 1-13, 2023
  43. N. Morrison, JD Nir, S. Norin, P. Rzążewski, A. Wesolek, Every graph is eventually Turan-good, Journal of Combinatorial Theory, Ser. B 162, pp. 231-243, 2023
  44. K.K. Dabrowski, T. Masařík, J. Novotná, D. Paulusma, P. Rzążewski, Clique-Width: Harnessing the Power of Atoms, Journal of Graph Theory 104, pp. 769-810, 2023
  45. J. Bok, J. Fiala, N. Jedličková, J. Kratochvíl, P. Rzążewski, List covering of regular multigraphs with semi-edges, Algorithmica 86, pp. 782 - 807, 2024
  46. T. Abrishami, M. Chudnovsky, S. Hajebi, P. Rzążewski, S. Spirkl, K. Vusković, Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree, Journal of Combinatorial Theory ser. B 164, pp. 371-403, 2024
  47. K. Łyczek, M. Nazarczuk, P. Rzążewski, Towards the Chen-Raspaud conjecture, Discrete Mathematics 347, 113789, 2024
  48. J. Focke, D. Marx, P. Rzążewski, Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds, ACM Transactions in Algorithms 20, pp. 11:1-11:32, 2024
  49. K. Majewski, T. Masařík, J. Novotna, K. Okrasa, M. 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, ACM Transactions of Computation Theory 16, 8:1-8:18, 2024
  50. T. Abrishami, M. Chudnovsky, Ma. Pilipczuk, P. Rzążewski, P. Seymour, Induced subgraphs of bounded treewidth and the container method, SIAM Journal on Computing 53, pp. 624-647, 2024
  51. G. Paesani, D. Paulusma, P. Rzążewski, Classifying Subset Feedback Vertex Set for H-free graphs, Theoretical Computer Science 1003, 2024
  52. J. Gajarský, L. Jaffke, P. Lima, J. Novotná, Ma. Pilipczuk, P. Rzążewski, U. Souza, Taming graphs with no large creatures and skinny ladders, to appear in SIAM J, Discrete Math., 2024
  53. A. Agrawal, P.T. Lima, D. Lokshtanov, P. Rzążewski, S. Saubrabh, R. Sharma, Odd Cycle Transversal on P_5-free Graphs in Polynomial Time, to appear in ACM Transactions on Algorithms

Reviewed conference proceedings

  1. K. Junosza-Szaniawski, P. Rzążewski, On Improved Exact Algorithms for L(2,1)-labeling of Graphs, IWOCA 2010 Proc., LNCS 6460, pp. 34–37, 2011 (DOI: 10.1007/978-3-642-19222-7)
  2. K. Junosza-Szaniawski, J. Kratochvil, M. Liedloff, P. Rossmanith, P. Rzążewski, Fast Exact Algorithm for L(2,1)-Labeling of Graphs, TAMC 2011 Proc., LNCS 6648, pp. 82-93 (DOI: 10.1007/978-3-642-20877-5)
  3. K. Junosza-Szaniawski, J. Kratochvil, M. Liedloff, P. Rzążewski, Determining the L(2,1)-span in Polynomial Space, WG 2012 Proc., LNCS  7551, pp. 126-137, 2012
  4. K. Kaczmarski, P. Rzążewski, Thrust and CUDA in data intensive algorithms, GID 2012 Proc., AISC 185, pp. 37-46, 2012
  5. K. Junosza-Szaniawski, J. Kratochvil, M. Pergel, P. Rzążewski, Beyond homothetic polygons: recognition and maximum clique, ISAAC 2012 Proc., LNCS 7676, pp. 619-628, 2012
  6. K. Kaczmarski, P. Przymus, P. Rzążewski, Improving High-Performance GPU Graph Traversal with Compression, GID 2014 Proc., AISC 312, pp. 201-214, 2015
  7. K. Junosza-Szaniawski, M. Liedloff, P. Rzążewski, Fixing improper coloring of graphs, SOFSEM 2015 Proc., LNCS 8939, pp. 266-276, 2015
  8. K. Kaczmarski, P. Rzążewski, A. Wolant, Massively parallel construction of the cell graph, PPAM 2015 Proc., Part I, LNCS 9573, pp. 559-569, 2016
  9. M. Dębski, Z. Lonc, P. Rzążewski, Sequences of radius k for complete bipartite graphs, WG 2016 Proc., LNCS 9941, pp. 1-12, 2016
  10. M. Pergel, P. Rzążewski, On edge intersection graphs of paths with 2 bends, WG 2016 Proc., LNCS 9941, pp. 207-219, 2016 (DOI: 10.1007/978-3-662-53536-3_18)
  11. É. Bonnet, T. Miltzow, P. Rzążewski, Complexity of Token Swapping and its Variants, STACS 2017 Proc. 16:1-16:14, 2017 (DOI: 10.4230/LIPIcs.STACS.2017.16)
  12. Cs. Biró, É. Bonnet, D. Marx, T. Miltzow, P. Rzążewski, Fine-grained complexity of coloring unit disks and balls, SOCG 2017 Proc. 18:1-18:16, 2017 (DOI: 10.4230/LIPIcs.SoCG.2017.18)
  13. L. Egri, D. Marx, P. Rzążewski, Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization, STACS 2018 Proc. LIPIcs 96, 27:1--27:15, 2018 (DOI: 10.4230/LIPIcs.STACS.2018.27)
  14. É. Bonnet, P. Rzążewski, F. Sikora, Designing RNA Secondary structures is Hard, RECOMB 2018 Proc. LNBI 10812, pp. 248--250
  15. É. Bonnet, P. Giannopoulos, E. J. Kim, P. Rzążewski, F. Sikora, QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs, SoCG 2018 Proc., 12:1--12:15, 2018 (DOI: 10.4230/LIPIcs.SoCG.2018.12)
  16. É. Bonnet, P. Rzążewski, Optimality Program in String and Segment Graphs, WG 2018 Proc., LNCS 11159, pp. 164-175, 2018 (DOI: 10.1007/978-3-030-00256-5_14)
  17. M.G. Dobbins, L. Kleist, T. Milltzow, P. Rzążewski,∀∃R-completeness and area-universality, WG 2018 Proc., LNCS 11159, pp. 79-90, 2018 (DOI: 10.1007/978-3-030-00256-5_7)
  18. K. Okrasa, P. Rzążewski, Subexponential algorithms for variants of homomorphism problem in string graphs, WG 2019 Proc., LNCS 11789, pp. 1--13, 2019
  19. M. Chudnovsky, S. Huang, P. Rzążewski, S. Spirkl, M. Zhong, Complexity of Ck-coloring in hereditary classes of graphs, ESA 2019 Proc., 31:1--31:15, 2019
  20. T. Masarik, I. Muzi, Ma. Pilipczuk, P. Rzążewski, M. Sorge, Packing directed circuits quarter-integrally , ESA 2019 Proc., 72:1--72:13, 2019
  21. J. Novotna, K. Okrasa, Mi. Pilipczuk, P. Rzążewski, E.J. van Leeuwen, B. Walczak, Subexponential-time algorithms for finding large induced sparse subgraphs, IPEC 2019 Proc., 23:1 -- 23:11, 2019  (DOI: 10.4230/LIPIcs.IPEC.2019.23)
  22. W. Evans, P. Rzążewski, N. Saeedi, C.-S. Shin, A. Wolff, Representing Graphs and Hypergraphs by Touching Polygons in 3d, GD 2019 Proc., LNCS 11904, pp. 18--32, 2019
  23. K. Okrasa, P. Rzążewski, Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs, SODA 2020 Proc., pp. 1578--1590, 2020
  24. P. Dvořák, A.E. Feldmann, A. Rai, P. Rzążewski, Parameterized Inapproximability of Independent Sets in H-Free Graphs, WG 2020 Proc., LNCS 12301, pp. 40-53, 2020
  25. K.K. Dabrowski, T. Masařík, J. Novotná, D. Paulusma, P. Rzążewski, Clique-Width: Harnessing the Power of Atoms, WG 2020 Proc., LNCS 12301, pp. 119-133, 2020
  26. K. Okrasa, M. Piecyk, P. Rzążewski, Full complexity classification of the list homomorphism problem for bounded-treewidth graphs, ESA 2020 Proc., 74:1 -- 74:24, 2020 (DOI: 10.4230/LIPIcs.ESA.2020.74)
  27. M. Chudnovsky, J. King, Mi. Pilipczuk, P. Rzążewski, S. Spirkl, Finding large H-colorable subgraphs in hereditary graph classes, ESA 2020 Proc., 35:1 -- 35:17, 2020 (DOI: 10.4230/LIPIcs.ESA.2020.35)
  28. H. Chen, B.M.P. Jansen, K. Okrasa, A. Pieterse, P. Rzążewski, Sparsification Lower Bounds for List-H-Coloring, ISAAC 2020 Proc., 58:1 -- 58:17, 2020 (DOI: 10.4230/LIPIcs.ISAAC.2020.58)
  29. T. Abrishami, M. Chudnovsky, Ma. Pilipczuk, P. Rzążewski, P. Seymour, Induced subgraphs of bounded treewidth and the container method, SODA 2021 Proc., pp. 1948-1964, 2021
  30. Mi. Pilipczuk, Ma. Pilipczuk, P. Rzążewski, Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths, SOSA 2021 Proc., pp. 204-209, 2021
  31. M. Piecyk, P. Rzążewski, Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth, STACS 2021 Proc., 56:1 -- 56:17, 2021
  32. K. Okrasa, P. Rzążewski, Complexity of the list homomorphism problem in hereditary graph classes, STACS 2021 Proc., 54:1 -- 54.17, 2021
  33. P. Gartland, D. Lokshtanov, Ma. Pilipczuk, Mi. Pilipczuk, P. Rzążewski, Finding large induced sparse subgraphs in C_>t-free graphs in quasipolynomial time, STOC 2021 Proc.,  pp. 330-341, 2021
  34. M. Dębski, M. Piecyk, P. Rzążewski, Faster 3-coloring of small-diameter graphs, ESA 2021 Proc., pp. 37:1 -- 37:15, 2021
  35. G. Paesani, D. Paulusma, P. Rzążewski, Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs, MFCS 2021 Proc., 82:1 -- 82:14, 2021
  36. J. Focke, D. Marx, P. Rzążewski, Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds, SODA 2022 Proc.,  pp. 431-458, 2022
  37. T. Abrishami, M. Chudnovsky, C. Dibek, P. Rzążewski, Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws, SODA 2022 Proc.,  pp. 1448-1470, 2022
  38. J. Bok, J. Fiala, N. Jedličková, J. Kratochvíl, P. Rzążewski, List covering of regular multigraphs, IWOCA 2022 Proc., LNCS 13270, pp. 228-242
  39. K. Majewski, T. Masařík, J. Novotna, K. Okrasa, M. 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 Proc., pp. 93:1--93:19, 2022
  40. G. Paesani, D. Paulusma, P. Rzążewski, Classifying Subset Feedback Vertex Set for H-free graphs, WG 2022 Proc., LNCS 13453, pp. 412-424, 2022
  41. S. Kisfaludi-Bak, K. Okrasa, P. Rzążewski, Computing list homomorphisms in geometric intersection graphs, WG 2022 Proc., LNCS 13453, pp. 313-327, 2022
  42. J. Gajarský, L. Jaffke, P. Lima, J. Novotná, Ma. Pilipczuk, P. Rzążewski, U. Souza, Taming graphs with no large creatures and skinny ladders, ESA 2022 Proc., pp. 58:1-58:8, 2022
  43. P. Dvořák, M. Krawczyk, T. Masařík, J. Novotná, P. Rzążewski, and A. Żuk, List Locally Surjective Homomorphisms in Hereditary Graph Classes, ISAAC 2022 Proc., pp. 30:1 - 30:15, 2022
  44. M. Dębski, Z. Lonc, K. Okrasa, M. Piecyk, P. Rzążewski, Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws, ISAAC 2022 Proc., pp. 14:1-14:16, 2022
  45. G. Gutowski, K. Junosza-Szaniawski. F. Klesen, P. Rzążewski, A. Wolff, J. Zink, Coloring and Recognizing Directed Interval Graphs, ISAAC 2023 Proc., 36:1-36:14, 2023
  46. M. Chudnovsky, R. McCarty, M. Pilipczuk, M. Pilipczuk, P. Rzążewski, Sparse induced subgraphs in P6-free graphs, SODA 2024 Proc., pp. 5291-5299, 2024
  47. T. Abrishami, M. Chudnovsky, Ma. Pilipczuk, P. Rzążewski, Max Weight Independent Set in sparse graphs with no long claws, STACS 2024 Proc., LIPIcs 289, pp. 4:1-4:15, 2024
  48. P. Gartland, D. Lokshtanov, T. Masarik, M. Pilipczuk, M. Pilipczuk, P. Rzążewski, Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polinomial Time, STOC 2024 Proc., pp. 683-691, 2024
  49. C. Groenland, I. Mannens, J. Nederlof, M. Piecyk, P. Rzążewski, Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters, ICALP 2024 Proc., pp. 11:1 - 77:21, LIPIcs 297, 2024
  50. B. Can Esmer, J. Focke, D. Marx, P. Rzążewski, Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness, ICALP 2024 Proc., pp. 34:1 - 34:17, LIPIcs 297, 2024
  51. B. Can Esmer, J. Focke, D. Marx, P. Rzążewski, List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs, ESA 2024 Proc., pp. 39:1-39:20 LIPIcs 308, 2024
  52. P.T. Lima, M. Milanic, P. Mursic, K. Okrasa, P. Rzążewski, K. Storgel, Tree decompositions meet induced matchings: beyond Max Weight Independent Set, ESA 2024 Proc., pp. 85:1-85:17 LIPIcs 308, 2024
  53. J. Goedgebeur, J. Jooken, K. Okrasa, P. Rzążewski, O. Schaudt, Minimal obstructions to C5-coloring in hereditary graph classes, MFCS 2024 Proc., LIPIcs 306, pp. 55:1 - 55:15, 2024

Preprints and informal proceedings

  1. K. Junosza-Szaniawski, P. Rzążewski, On the number of 2-packings in a connected graph, KAM Series 2010, 991
  2. K. Junosza-Szaniawski, P. Rzążewski, On the Complexity of Exact Algorithm for L(2,1)-labeling of Graphs, KAM Series 2010, 992
  3. K. Junosza-Szaniawski, P. Rzążewski, Determining L(2,1)-span in Polynomial Space, arXiv:1104.4506 [cs.DM]
  4. P. Rzążewski, Exact Algorithm for Graph Homomorphism and Locally Injective Graph Homomorphism, arXiv:1310.3341 [cs.DM]
  5. K. Junosza-Szaniawski, P. Rzążewski, An Exact Algorithm for the Generalized List T-Coloring Problem, arXiv:1311.0603 [cs.DM]
  6. V.E. Brimkov, K. Junosza-Szaniawski, S. Kafer, J. Kratochvil, M. Pergel, P. Rzążewski, M. Szczepankiewicz, J. Terhaar, Homothetic Polygons and Beyond: Intersection Graphs, Recognition, Maximum Clique, arXiv:1411.2928 [cs.DM]
  7. K. Kaczmarski, P. Rzążewski, A. Wolant, Massively Parallel Construction of the Cell Graph, arXiv:1503.06029 [cs.DC]
  8. M. Dębski, Z. Lonc, P. Rzążewski, Harmonious and achromatic colorings of fragmentable hypergraphs, EUROCOMB 2015 Proc., ENDM 49, pp. 309-314, 2015
  9. K. Junosza-Szaniawski, P. Rzążewski, J. Sokół, K. Węsek, Coloring and L(2,1)-labeling of unit disk intersection graphs, EuroCG 2016 proc.
  10. V. Garnero, K. Junosza-Szaniawski, M. Liedloff, P. Montealegre, P. Rzążewski, Fixing improper colorings of graphs, arXiv:1607.06911 [cs.DM]
  11. É. Bonnet, T. Miltzow, P. Rzążewski, Complexity of Token Swapping and its Variants, arXiv:1607.07676 [cs.CC]
  12. Cs. Biró, É. Bonnet, D. Marx, T. Miltzow, P. Rzążewski, Fine-grained complexity of coloring unit disks and balls, EuroCG 2017 Proc., pp. 189-192
  13. L. Kleist, T. Milltozw, P. Rzążewski, Is Area Universality∀∃R-complete?, EuroCG 2017 Proc., pp. 181-184
  14. Z. Lonc, P. Naroski, P. Rzążewski, Tight Euler tours in uniform hypergraphs - computational aspects, arXiv:1706.09356 [cs.CC]
  15. É. Bonnet, P. Rzążewski, F. Sikora, Designing RNA Secondary Structures is Hard, arXiv:1710.11513 [cs.DS]
  16. M. Dębski, Z. Lonc, P. Rzążewski, Sequences of radius k for complete bipartite graphs, arXiv:1711.05091 [cs.DM]
  17. M. Pergel, P. Rzążewski, On edge intersection graphs of paths with 2 bends, arXiv:1711.05096 [cs.DM]
  18. M.G. Dobbins, L. Kleist, T. Milltozw, P. Rzążewski, ∀∃R-completeness and area-universality, arXiv:1712.05142 [cs.CG]
  19. É. Bonnet, P. Giannopoulos, E. J. Kim, P. Rzążewski, F. Sikora, QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs, arXiv:1712.05010 [cs.CG]
  20. É. Bonnet, P. Rzążewski, Optimality Program in String and Segment Graphs, arXiv:1712.08907 [cs.CG]
  21. É. Bonnet, P. Giannopoulos, E. J. Kim, P. Rzążewski, F. Sikora, QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs, EuroCG 2018 Proc.
  22. D. Dereniowski, D. Osula, P. Rzążewski, Finding small-width connected path decompositions in polynomial time, arXiv:a1802.0550 [cs.DS]
  23. K. Okrasa, P. Rzążewski, Intersecting edge distinguishing colorings of hypergraphs, arXiv:1804.10470 [cs.DM]
  24. C. Groenland, K. Okrasa, P. Rzążewski, A. Scott, P. Seymour, S. Spirkl, H-colouring Pt-free graphs in subexponential time, arXiv:1803.05396 [cs.DM]
  25. K. Okrasa, P. Rzążewski, Subexponential algorithms for variants of homomorphism problem in string graphs, arXiv: 1809.09345 [cs.CC]
  26. K. Okrasa, P. Rzążewski, Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs, arXiv: 1906.08371 [cs.CC]
  27. T. Masarik, I. Muzi, Ma. Pilipczuk, P. Rzążewski, M. Sorge, Packing directed circuits quarter-integrally, arXiv: 1907:02494 [cs.DM]
  28. K. Dabrowski, C. Feghali, M. Johnson, G. Paesani, D. Paulusma, P. Rzążewski, On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest, arXiv: 1908.00491 [cs.DS]
  29. W. Evans, P. Rzążewski, N. Saeedi, C.-S. Shin, A. Wolff, Representing Graphs and Hypergraphs by Touching Polygons in 3d, arXiv: 1908.08273 [cs.CG]
  30. J. Novotna, K. Okrasa, Mi. Pilipczuk, P. Rzążewski, E.J. van Leeuwen, B. Walczak, Subexponential-time algorithms for finding large induced sparse subgraphs, arXiv:1910.01082 [cs.CC]
  31. T. Abrishami, M. Chudnovsky, Ma. Pilipczuk, P. Rzążewski, P. Seymour, Induced subgraphs of bounded treewidth and the container method, arXiv:2003.05185 [cs.DS]
  32. M. Chudnovsky, J. King, Mi. Pilipczuk, P. Rzążewski, S. Spirkl, Finding large H-colorable subgraphs in hereditary graph classes, arXiv: 2004.09425 [cs.DS]
  33. M. Chudnovsky, S. Huang, P. Rzążewski, S. Spirkl, M. Zhong, Complexity of Ck-coloring in hereditary classes of graphs, arXiv: 2005.01824 [cs.DS]
  34. K.K. Dabrowski, T. Masařík, J. Novotná, D. Paulusma, P. Rzążewski, Clique-Width: Harnessing the Power of Atoms, arXiv: 2006.03578 [cs.DM]
  35. P. Dvořák, A.E. Feldmann, A. Rai, P. Rzążewski, Parameterized Inapproximability of Independent Sets in H-Free  Graphs, arXiv: 2006.10444 [cs.CC]
  36. K. Okrasa, M. Piecyk, P. Rzążewski, Full complexity classification of the list homomorphism problem for bounded-treewidth graphs, arXiv: 2006.11155 [cs.CC]
  37. H. Chen, B.M.P. Jansen, K. Okrasa, A. Pieterse, P. Rzążewski, Sparsification Lower Bounds for List-H-Coloring, arXiv: 2009.08353 [cs.CC]
  38. M. Piecyk, P. Rzążewski, Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth, arXiv: 2009.11642 [cs.CC]
  39. Mi. Pilipczuk, Ma. Pilipczuk, P. Rzążewski, Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths, arXiv: 2009.13494 [cs.DS]
  40. K. Okrasa, P. Rzążewski, Complexity of the list homomorphism problem in hereditary graph classes, arXiv: 2010.03393 [cs.CC]
  41. P. Gartland, D. Lokshtanov, Ma. Pilipczuk, Mi. Pilipczuk, P. Rzążewski, Finding large induced sparse subgraphs in C_>t-free graphs in quasipolynomial time, arXiv: 2007.11402 [cs.DS]
  42. M. Bonamy, N. Bousquet, M. Pilipczuk, P. Rzążewski, S. Thomasse, B. Walczak, Degeneracy of P_t-free and C_{>= t}-free graphs with no large complete bipartite subgraphs, arXiv:2012.03686 [math.CO]
  43. T. Masařík, M. Pilipczuk, P. Rzążewski, M. Sorge, Constant congestion brambles in directed graphs, arXiv: 2103.08445
  44. M. Dębski, M. Piecyk, P. Rzążewski, Faster 3-coloring of small-diameter graph, arXiv: 2104.13860
  45. T. Masařík, M. Pilipczuk, P. Rzążewski, M. Sorge, Constant congestion brambles in directed graphs, EUROCOMB 2021 Proc., Trends in Mathematics 14, 2021, pp. 318-324
  46. G. Paesani, D. Paulusma, P. Rzążewski, Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs, arXiv: 2105.02736
  47. M. Krzyziński, P. Rzążewski, Sz. Tur, Coloring squares of planar graphs with small maximum degree, arXiv: 2105.11235
  48. T. Abrishami, M. Chudnovsky, S. Hajebi, P. Rzążewski, S. Spirkl, K. Vusković, Toward induced subgraph obstructions to bounded treewidth, arXiv: 2108:01162
  49. T. Abrishami, M. Chudnovsky, C. Dibek, P. Rzążewski, Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws, arXiv:2107.05434
  50. J. Focke, D. Marx, P. Rzążewski, Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds, arXiv: 2107.06889
  51. M. Bonamy, É. Bonnet, N. Bousquet, O. Charbit, P. Giannopoulos, E-J. Kim, P. Rzążewski, F. Sikora, S. Thomasse, EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs, arXiv: 2110.15419
  52. G. Paesani, D. Paulusma, P. Rzążewski, Classifying Subset Feedback Vertex Set for H-free graphs, arXiv: 2201.00430
  53. S. Kisfaludi-Bak, K. Okrasa, P. Rzążewski, Computing list homomorphisms in geometric intersection graphs, arXiv: 2202.08896
  54. P. Dvořák, M. Krawczyk, T. Masařík, J. Novotná, P. Rzążewski, and A. Żuk, List Locally Surjective Homomorphisms in Hereditary Graph Classes, arXiv 2202.12438
  55. K. Majewski, T. Masařík, J. Novotna, K. Okrasa, M. 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, arXiv 2203.04836
  56. J. Bok, J. Fiala, N. Jedličková, J. Kratochvíl, P. Rzążewski, List covering of regular multigraphs, arXiv 2204.04280
  57. M. Dębski, Z. Lonc, K. Okrasa, M. Piecyk, P. Rzążewski, Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws, arXiv:2205.13270
  58. N. Morrison, JD Nir, S. Norin, P. Rzążewski, A. Wesolek, Every graph is eventually Turan-good, arXiv 2208.08499
  59. M. Milanič, P. Rzążewski, Tree decompositions with bounded independence number: beyond independent sets, arXiv:2209.12315
  60. B. Can Esmer, J. Focke, D. Marx, P. Rzążewski, List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs, arXiv:2210.10677
  61. G. Gutowski, K. Junosza-Szaniawski. F. Klesen, P. Rzążewski, A. Wolff, J. Zink, Coloring and Recognizing Directed Interval Graphs, arXiv:2303.07960
  62. P. Gartland, D. Lokshtanov, T. Masarik, M. Pilipczuk, M. Pilipczuk, P. Rzążewski, Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polinomial Time, arXiv:2305.15738
  63. M. Chudnovsky, R. McCarty, M. Pilipczuk, M. Pilipczuk, P. Rzążewski, Sparse induced subgraphs in P6-free graphs, arXiv:2307.07330
  64. T. Abrishami, M. Chudnovsky, Ma. Pilipczuk, P. Rzążewski, Max Weight Independent Set in sparse graphs with no long claws, arXiv:2309.16995
  65. M. Pilipczuk, P. Rzążewski, A polynomial bound on the number of minimal separators and potential maximal cliques in P6-free graphs of bounded clique number, arXiv:2310,11573
  66. C. Groenland, I. Mannens, J. Nederlof, M. Piecyk, P. Rzążewski, Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters, arXiv:2312.03859
  67. B. Can Esmer, J. Focke, D. Marx, P. Rzążewski, As Good as It Gets: Which Optimization Problems Require Brute Force, Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness, arXiv:2402.07331
  68. A. Agrawal, P.T. Lima, D. Lokshtanov, P. Rzążewski, S. Saubrabh, R. Sharma, Odd Cycle Transversal on P_5-free Graphs in Polynomial Time, arXiv:2402.11465
  69. P.T. Lima, M. Milanic, P. Mursic, K. Okrasa, P. Rzążewski, K. Storgel, Tree decompositions meet induced matchings: beyond Max Weight Independent Set, arXiv:2402.15834
  70. J. Goedgebeur, J. Jooken, K. Okrasa, O. Schaudt, P. Rzążewski, Minimal obstructions to C5-coloring in hereditary graph classes, arXiv:2404.11704
  71. T. Abrishami, M. Briański, J. Czyżewska, R. McCarty, M. Milanic, P. Rzążewski, B. Walczak, Excluding a clique or a biclique in graphs of bounded induced matching treewidth, arXiv:2405.04617
  72. E. Bonnet, P. Rzążewski, An 11/6 Approximation Algorithm for Vertex Cover on String Graphs, arXiv:2409.18820
  73. D. Lokshtanov, P. Rzążewski, S. Saurabh, R. Sharma, M. Zehavi, Maximum Partial List H-Coloring on P_5-free graphs in polynomial time, arXiv:2410.21569

Manuscripts

  1. Ma Pilipczuk, P. Rzążewski, A polynomial bound on the number of minimal separators and potential maximal cliques in P6-free graphs of bounded clique number (submitted)
  2. M. Chudnovsky, R. McCarty, M. Pilipczuk, M. Pilipczuk, P. Rzążewski, Sparse induced subgraphs in P6-free graphs (submitted)
  3. T. Abrishami, M. Briański, J. Czyżewska, R. McCarty, M. Milanic, P. Rzążewski, B. Walczak, Excluding a clique or a biclique in graphs of bounded induced matching treewidth (submitted)
  4. T. Abrishami, M. Chudnovsky, C. Dibek, M. Pilipczuk, P. Rzążewski, Max Weight Independent Set in sparse graphs with no long claws (submitted)
  5. M. Chudnovsky, J. Czyżewska, K. Kluk, M. Pilipczuk, P. Rzążewski, Sparse induced subgraphs in P7-free graphs of bounded clique number (submitted)
  6. J. Goedgebeur, J. Jooken, K. Okrasa, P. Rzążewski, O. Schaudt, Minimal obstructions to C5-coloring in hereditary graph classes (submitted)
  7. P.T. Lima, M. Milanic, P. Mursic, K. Okrasa, P. Rzążewski, K. Storgel, Tree decompositions meet induced matchings: beyond Max Weight Independent Set (submitted)
  8. D. Lokshtanov, P. Rzążewski, S. Saurabh, R. Sharma, M. Zehavi, Maximum Partial List H-Coloring on P_5-free graphs in polynomial time (submitted)

Other

  1. I. Herburt, P. Rzążewski, Interpolacja fraktalna, czyli dwukrotne fałszerstwo na zamówienie, Delta 07/2011 (446), pp. 14-15
  2. Ł. Kowalik, M. Pilipczuk, P. Rzążewski (editors), 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers
  3. E. Bonnet, P. Rzążewski (editors), 19th International Symposium on Parameterized and Exact Computation (IPEC 2024), LIPIcs, Volume 321 (2024)

My dblp webpage


Powered by CMSimple