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 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Michał Dębski, Marta Piecyk, and Paweł Rzążewski. Faster 3-Coloring of Small-Diameter Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 37:1-37:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{debski_et_al:LIPIcs.ESA.2021.37, author = {D\k{e}bski, Micha{\l} and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Faster 3-Coloring of Small-Diameter Graphs}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {37:1--37:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.37}, URN = {urn:nbn:de:0030-drops-146181}, doi = {10.4230/LIPIcs.ESA.2021.37}, annote = {Keywords: 3-coloring, fine-grained complexity, subexponential-time algorithm, diameter} }
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 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} }
Feedback for Dagstuhl Publishing