Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Tatsuya Gima and Yota Otachi. Extended MSO Model Checking via Small Vertex Integrity. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 20:1-20:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gima_et_al:LIPIcs.ISAAC.2022.20, author = {Gima, Tatsuya and Otachi, Yota}, title = {{Extended MSO Model Checking via Small Vertex Integrity}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {20:1--20:15}, 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.20}, URN = {urn:nbn:de:0030-drops-173056}, doi = {10.4230/LIPIcs.ISAAC.2022.20}, annote = {Keywords: vertex integrity, monadic second-order logic, cardinality constraint, fixed-parameter tractability} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Michael Lampis and Valia Mitsou. Fine-Grained Meta-Theorems for Vertex Integrity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 34:1-34:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{lampis_et_al:LIPIcs.ISAAC.2021.34, author = {Lampis, Michael and Mitsou, Valia}, title = {{Fine-Grained Meta-Theorems for Vertex Integrity}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {34:1--34:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.34}, URN = {urn:nbn:de:0030-drops-154674}, doi = {10.4230/LIPIcs.ISAAC.2021.34}, annote = {Keywords: Model-Checking, Fine-grained complexity, Vertex Integrity} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy Distinguishes Treewidth from Pathwidth. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 14:1-14:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{belmonte_et_al:LIPIcs.ESA.2020.14, author = {Belmonte, R\'{e}my and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and Otachi, Yota}, title = {{Grundy Distinguishes Treewidth from Pathwidth}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {14:1--14:19}, 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.14}, URN = {urn:nbn:de:0030-drops-128803}, doi = {10.4230/LIPIcs.ESA.2020.14}, annote = {Keywords: Treewidth, Pathwidth, Clique-width, Grundy Coloring} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, and Théo Pierron. Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 15:1-15:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{foucaud_et_al:LIPIcs.IPEC.2019.15, author = {Foucaud, Florent and Hocquard, Herv\'{e} and Lajou, Dimitri and Mitsou, Valia and Pierron, Th\'{e}o}, title = {{Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {15:1--15:16}, 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.15}, URN = {urn:nbn:de:0030-drops-114765}, doi = {10.4230/LIPIcs.IPEC.2019.15}, annote = {Keywords: Graph homomorphism, Graph modification, Edge-coloured graph, Signed graph} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora. Token Sliding on Split Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 13:1-13:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{belmonte_et_al:LIPIcs.STACS.2019.13, author = {Belmonte, R\'{e}my and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and Otachi, Yota and Sikora, Florian}, title = {{Token Sliding on Split Graphs}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.13}, URN = {urn:nbn:de:0030-drops-102529}, doi = {10.4230/LIPIcs.STACS.2019.13}, annote = {Keywords: reconfiguration, independent set, split graph} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Michael Lampis and Valia Mitsou. Treewidth with a Quantifier Alternation Revisited. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 26:1-26:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{lampis_et_al:LIPIcs.IPEC.2017.26, author = {Lampis, Michael and Mitsou, Valia}, title = {{Treewidth with a Quantifier Alternation Revisited}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {26:1--26:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.26}, URN = {urn:nbn:de:0030-drops-85512}, doi = {10.4230/LIPIcs.IPEC.2017.26}, annote = {Keywords: Treewidth, Exponential Time Hypothesis, Quantified SAT} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Rémy Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (Approximate) Defective Coloring. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 10:1-10:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{belmonte_et_al:LIPIcs.STACS.2018.10, author = {Belmonte, R\'{e}my and Lampis, Michael and Mitsou, Valia}, title = {{Parameterized (Approximate) Defective Coloring}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {10:1--10: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.10}, URN = {urn:nbn:de:0030-drops-85304}, doi = {10.4230/LIPIcs.STACS.2018.10}, annote = {Keywords: Treewidth, Parameterized Complexity, Approximation, Coloring} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Dániel Marx and Valia Mitsou. Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 28:1-28:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{marx_et_al:LIPIcs.ICALP.2016.28, author = {Marx, D\'{a}niel and Mitsou, Valia}, title = {{Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {28:1--28:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.28}, URN = {urn:nbn:de:0030-drops-63078}, doi = {10.4230/LIPIcs.ICALP.2016.28}, annote = {Keywords: Parameterized Complexity, List coloring, Treewidth, Lower bounds under ETH} }
Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)
Jean-Francois Baffier, Man-Kwun Chiu, Yago Diez, Matias Korman, Valia Mitsou, André van Renssen, Marcel Roeloffzen, and Yushi Uno. Hanabi is NP-complete, Even for Cheaters who Look at Their Cards. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 4:1-4:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{baffier_et_al:LIPIcs.FUN.2016.4, author = {Baffier, Jean-Francois and Chiu, Man-Kwun and Diez, Yago and Korman, Matias and Mitsou, Valia and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Uno, Yushi}, title = {{Hanabi is NP-complete, Even for Cheaters who Look at Their Cards}}, booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)}, pages = {4:1--4:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-005-7}, ISSN = {1868-8969}, year = {2016}, volume = {49}, editor = {Demaine, Erik D. and Grandoni, Fabrizio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.4}, URN = {urn:nbn:de:0030-drops-58644}, doi = {10.4230/LIPIcs.FUN.2016.4}, annote = {Keywords: algorithmic combinatorial game theory, sorting} }
Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and Approximability of Parameterized MAX-CSPs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 294-306, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{dell_et_al:LIPIcs.IPEC.2015.294, author = {Dell, Holger and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and M\"{o}mke, Tobias}, title = {{Complexity and Approximability of Parameterized MAX-CSPs}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {294--306}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.294}, URN = {urn:nbn:de:0030-drops-55910}, doi = {10.4230/LIPIcs.IPEC.2015.294}, annote = {Keywords: Approximation, Structural Parameters, Constraint Satisfaction} }
Feedback for Dagstuhl Publishing