Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink. Coloring and Recognizing Mixed Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gutowski_et_al:LIPIcs.ISAAC.2023.36, author = {Gutowski, Grzegorz and Junosza-Szaniawski, Konstanty and Klesen, Felix and Rz\k{a}\.{z}ewski, Pawe{\l} and Wolff, Alexander and Zink, Johannes}, title = {{Coloring and Recognizing Mixed Interval Graphs}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {36:1--36:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.36}, URN = {urn:nbn:de:0030-drops-193388}, doi = {10.4230/LIPIcs.ISAAC.2023.36}, annote = {Keywords: Interval Graphs, Mixed Graphs, Graph Coloring} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{debski_et_al:LIPIcs.ISAAC.2022.14, author = {D\k{e}bski, Micha{\l} and Lonc, Zbigniew and Okrasa, Karolina and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {14:1--14:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.14}, URN = {urn:nbn:de:0030-drops-172996}, doi = {10.4230/LIPIcs.ISAAC.2022.14}, annote = {Keywords: graph homomorphism, forbidden induced subgraphs, precoloring extension} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, and Kirill Simonov. The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 66:1-66:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ganian_et_al:LIPIcs.ICALP.2022.66, author = {Ganian, Robert and Hamm, Thekla and Korchemna, Viktoriia and Okrasa, Karolina and Simonov, Kirill}, title = {{The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {66:1--66:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.66}, URN = {urn:nbn:de:0030-drops-164076}, doi = {10.4230/LIPIcs.ICALP.2022.66}, annote = {Keywords: homomorphism, clique-width, fine-grained complexity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, and Marek Sokołowski. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 93:1-93:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{majewski_et_al:LIPIcs.ICALP.2022.93, author = {Majewski, Konrad and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana and Okrasa, Karolina and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Soko{\l}owski, Marek}, title = {{Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gy\'{a}rf\'{a}s' Path Argument}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {93:1--93:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.93}, URN = {urn:nbn:de:0030-drops-164343}, doi = {10.4230/LIPIcs.ICALP.2022.93}, annote = {Keywords: Max Independent Set, subdivided claw, QPTAS, subexponential-time algorithm} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Karolina Okrasa and Paweł Rzążewski. Complexity of the List Homomorphism Problem in Hereditary Graph Classes. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{okrasa_et_al:LIPIcs.STACS.2021.54, author = {Okrasa, Karolina and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Complexity of the List Homomorphism Problem in Hereditary Graph Classes}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {54:1--54:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.54}, URN = {urn:nbn:de:0030-drops-136990}, doi = {10.4230/LIPIcs.STACS.2021.54}, annote = {Keywords: list homomorphism, fine-grained complexity, hereditary graph classes} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Marta Piecyk and Paweł Rzążewski. Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{piecyk_et_al:LIPIcs.STACS.2021.56, author = {Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {56:1--56:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.56}, URN = {urn:nbn:de:0030-drops-137012}, doi = {10.4230/LIPIcs.STACS.2021.56}, annote = {Keywords: list homomorphisms, fine-grained complexity, SETH, feedback vertex set, cutwidth} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, and Karolina Okrasa. Vertex Deletion into Bipartite Permutation Graphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bozyk_et_al:LIPIcs.IPEC.2020.5, author = {Bo\.{z}yk, {\L}ukasz and Derbisz, Jan and Krawczyk, Tomasz and Novotn\'{a}, Jana and Okrasa, Karolina}, title = {{Vertex Deletion into Bipartite Permutation Graphs}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {5:1--5:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.5}, URN = {urn:nbn:de:0030-drops-133087}, doi = {10.4230/LIPIcs.IPEC.2020.5}, annote = {Keywords: permutation graphs, comparability graphs, partially ordered set, graph modification problems} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzążewski. Sparsification Lower Bounds for List H-Coloring. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chen_et_al:LIPIcs.ISAAC.2020.58, author = {Chen, Hubie and Jansen, Bart M. P. and Okrasa, Karolina and Pieterse, Astrid and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Sparsification Lower Bounds for List H-Coloring}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {58:1--58:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.58}, URN = {urn:nbn:de:0030-drops-134027}, doi = {10.4230/LIPIcs.ISAAC.2020.58}, annote = {Keywords: List H-Coloring, Sparsification, Constraint Satisfaction Problem} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge. The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bellitto_et_al:LIPIcs.ISAAC.2020.59, author = {Bellitto, Thomas and Li, Shaohua and Okrasa, Karolina and Pilipczuk, Marcin and Sorge, Manuel}, title = {{The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {59:1--59:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.59}, URN = {urn:nbn:de:0030-drops-134036}, doi = {10.4230/LIPIcs.ISAAC.2020.59}, annote = {Keywords: Graph algorithms, fixed-parameter tractability, parameterized complexity} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 74:1-74:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{okrasa_et_al:LIPIcs.ESA.2020.74, author = {Okrasa, Karolina and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {74:1--74:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.74}, URN = {urn:nbn:de:0030-drops-129402}, doi = {10.4230/LIPIcs.ESA.2020.74}, annote = {Keywords: list homomorphisms, fine-grained complexity, SETH, treewidth} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, and Bartosz Walczak. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 23:1-23:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{novotna_et_al:LIPIcs.IPEC.2019.23, author = {Novotn\'{a}, Jana and Okrasa, Karolina and Pilipczuk, Micha{\l} and Rz\k{a}\.{z}ewski, Pawe{\l} and van Leeuwen, Erik Jan and Walczak, Bartosz}, title = {{Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {23:1--23:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.23}, URN = {urn:nbn:de:0030-drops-114845}, doi = {10.4230/LIPIcs.IPEC.2019.23}, annote = {Keywords: subexponential algorithm, feedback vertex set, P\underlinet-free graphs, string graphs} }
Feedback for Dagstuhl Publishing