Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Michael Lampis and Manolis Vasilakis. Structural Parameterizations for Two Bounded Degree Problems Revisited. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 77:1-77:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lampis_et_al:LIPIcs.ESA.2023.77, author = {Lampis, Michael and Vasilakis, Manolis}, title = {{Structural Parameterizations for Two Bounded Degree Problems Revisited}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {77:1--77:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.77}, URN = {urn:nbn:de:0030-drops-187302}, doi = {10.4230/LIPIcs.ESA.2023.77}, annote = {Keywords: ETH, Parameterized Complexity, SETH} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Michael Lampis, Nikolaos Melissinos, and Manolis Vasilakis. Parameterized Max Min Feedback Vertex Set. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lampis_et_al:LIPIcs.MFCS.2023.62, author = {Lampis, Michael and Melissinos, Nikolaos and Vasilakis, Manolis}, title = {{Parameterized Max Min Feedback Vertex Set}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {62:1--62:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.62}, URN = {urn:nbn:de:0030-drops-185965}, doi = {10.4230/LIPIcs.MFCS.2023.62}, annote = {Keywords: ETH, Feedback vertex set, Parameterized algorithms, Treewidth} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Michael Lampis. First Order Logic on Pathwidth Revisited Again. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 132:1-132:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lampis:LIPIcs.ICALP.2023.132, author = {Lampis, Michael}, title = {{First Order Logic on Pathwidth Revisited Again}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {132:1--132:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.132}, URN = {urn:nbn:de:0030-drops-181848}, doi = {10.4230/LIPIcs.ICALP.2023.132}, annote = {Keywords: Algorithmic Meta-Theorems, FO logic, Pathwidth} }
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-dev.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 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Tesshu Hanaka and Michael Lampis. Hedonic Games and Treewidth Revisited. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hanaka_et_al:LIPIcs.ESA.2022.64, author = {Hanaka, Tesshu and Lampis, Michael}, title = {{Hedonic Games and Treewidth Revisited}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {64:1--64:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.64}, URN = {urn:nbn:de:0030-drops-170025}, doi = {10.4230/LIPIcs.ESA.2022.64}, annote = {Keywords: Hedonic Games, Nash Equilibrium, Treewidth} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Michael Lampis. Determining a Slater Winner Is Complete for Parallel Access to NP. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lampis:LIPIcs.STACS.2022.45, author = {Lampis, Michael}, title = {{Determining a Slater Winner Is Complete for Parallel Access to NP}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {45:1--45:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.45}, URN = {urn:nbn:de:0030-drops-158555}, doi = {10.4230/LIPIcs.STACS.2022.45}, annote = {Keywords: Slater winner, Feedback Arc Set, Tournaments} }
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-dev.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 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Laurent Gourvès, Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos. Filling Crosswords Is Very Hard. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{gourves_et_al:LIPIcs.ISAAC.2021.36, author = {Gourv\`{e}s, Laurent and Harutyunyan, Ararat and Lampis, Michael and Melissinos, Nikolaos}, title = {{Filling Crosswords Is Very Hard}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {36:1--36:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.36}, URN = {urn:nbn:de:0030-drops-154690}, doi = {10.4230/LIPIcs.ISAAC.2021.36}, annote = {Keywords: Crossword Puzzle, Treewidth, ETH} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Júlio Araújo, Marin Bougeret, Victor Campos, and Ignasi Sau. A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{araujo_et_al:LIPIcs.IPEC.2021.4, author = {Ara\'{u}jo, J\'{u}lio and Bougeret, Marin and Campos, Victor and Sau, Ignasi}, title = {{A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.4}, URN = {urn:nbn:de:0030-drops-153879}, doi = {10.4230/LIPIcs.IPEC.2021.4}, annote = {Keywords: Maximum minimal vertex cover, parameterized complexity, polynomial kernel, kernelization lower bound, Erd\H{o}s-Hajnal property, induced subgraphs} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Michael Lampis. Minimum Stable Cut and Treewidth. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 92:1-92:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{lampis:LIPIcs.ICALP.2021.92, author = {Lampis, Michael}, title = {{Minimum Stable Cut and Treewidth}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {92:1--92:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.92}, URN = {urn:nbn:de:0030-drops-141616}, doi = {10.4230/LIPIcs.ICALP.2021.92}, annote = {Keywords: Treewidth, Local Max-Cut, Nash Stability} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos. Digraph Coloring and Distance to Acyclicity. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{harutyunyan_et_al:LIPIcs.STACS.2021.41, author = {Harutyunyan, Ararat and Lampis, Michael and Melissinos, Nikolaos}, title = {{Digraph Coloring and Distance to Acyclicity}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {41:1--41:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.41}, URN = {urn:nbn:de:0030-drops-136865}, doi = {10.4230/LIPIcs.STACS.2021.41}, annote = {Keywords: Digraph Coloring, Dichromatic number, NP-completeness, Parameterized complexity, Feedback vertex and arc sets} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. New Algorithms for Mixed Dominating Set. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dublois_et_al:LIPIcs.IPEC.2020.9, author = {Dublois, Louis and Lampis, Michael and Paschos, Vangelis Th.}, title = {{New Algorithms for Mixed Dominating Set}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {9:1--9:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.9}, URN = {urn:nbn:de:0030-drops-133127}, doi = {10.4230/LIPIcs.IPEC.2020.9}, annote = {Keywords: FPT Algorithms, Exact Algorithms, Mixed Domination} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Yasuaki Kobayashi and Yota Otachi. Parameterized Complexity of Graph Burning. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 21:1-21:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kobayashi_et_al:LIPIcs.IPEC.2020.21, author = {Kobayashi, Yasuaki and Otachi, Yota}, title = {{Parameterized Complexity of Graph Burning}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {21:1--21:10}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.21}, URN = {urn:nbn:de:0030-drops-133241}, doi = {10.4230/LIPIcs.IPEC.2020.21}, annote = {Keywords: Graph burning, parameterized complexity, fixed-parameter tractability} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos. (In)approximability of Maximum Minimal FVS. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dublois_et_al:LIPIcs.ISAAC.2020.3, author = {Dublois, Louis and Hanaka, Tesshu and Khosravian Ghadikolaei, Mehdi and Lampis, Michael and Melissinos, Nikolaos}, title = {{(In)approximability of Maximum Minimal FVS}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {3:1--3:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.3}, URN = {urn:nbn:de:0030-drops-133477}, doi = {10.4230/LIPIcs.ISAAC.2020.3}, annote = {Keywords: Approximation Algorithms, ETH, Inapproximability} }
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-dev.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} }
Feedback for Dagstuhl Publishing