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 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
László Egri, Dániel Marx, and Pawel Rzazewski. Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 27:1-27:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{egri_et_al:LIPIcs.STACS.2018.27, author = {Egri, L\'{a}szl\'{o} and Marx, D\'{a}niel and Rzazewski, Pawel}, title = {{Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.27}, URN = {urn:nbn:de:0030-drops-84867}, doi = {10.4230/LIPIcs.STACS.2018.27}, annote = {Keywords: graph homomorphism, list homomorphism, reflexive graph, treewidth} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Édouard Bonnet, László Egri, and Dániel Marx. Fixed-Parameter Approximability of Boolean MinCSPs. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 18:1-18:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{bonnet_et_al:LIPIcs.ESA.2016.18, author = {Bonnet, \'{E}douard and Egri, L\'{a}szl\'{o} and Marx, D\'{a}niel}, title = {{Fixed-Parameter Approximability of Boolean MinCSPs}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {18:1--18:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.18}, URN = {urn:nbn:de:0030-drops-63694}, doi = {10.4230/LIPIcs.ESA.2016.18}, annote = {Keywords: constraint satisfaction problems, approximability, fixed-parameter tractability} }
Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)
Laszlo Egri. On Constraint Satisfaction Problems below P. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 203-217, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@InProceedings{egri:LIPIcs.CSL.2011.203, author = {Egri, Laszlo}, title = {{On Constraint Satisfaction Problems below P}}, booktitle = {Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL}, pages = {203--217}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-32-3}, ISSN = {1868-8969}, year = {2011}, volume = {12}, editor = {Bezem, Marc}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.203}, URN = {urn:nbn:de:0030-drops-32320}, doi = {10.4230/LIPIcs.CSL.2011.203}, annote = {Keywords: constraint satisfaction problems, complexity classes, Datalog fragments} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
László Egri, Andrei Krokhin, Benoit Larose, and Pascal Tesson. The Complexity of the List Homomorphism Problem for Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 335-346, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{egri_et_al:LIPIcs.STACS.2010.2467, author = {Egri, L\'{a}szl\'{o} and Krokhin, Andrei and Larose, Benoit and Tesson, Pascal}, title = {{The Complexity of the List Homomorphism Problem for Graphs}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {335--346}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2467}, URN = {urn:nbn:de:0030-drops-24675}, doi = {10.4230/LIPIcs.STACS.2010.2467}, annote = {Keywords: Graph homomorphism, constraint satisfaction problem, complexity, universal algebra, Datalog} }
Feedback for Dagstuhl Publishing