Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, and Alina Vdovina. Parameterized (Modular) Counting and Cayley Graph Expanders. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 84:1-84:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{peyerimhoff_et_al:LIPIcs.MFCS.2021.84, author = {Peyerimhoff, Norbert and Roth, Marc and Schmitt, Johannes and Stix, Jakob and Vdovina, Alina}, title = {{Parameterized (Modular) Counting and Cayley Graph Expanders}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {84:1--84:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.84}, URN = {urn:nbn:de:0030-drops-145246}, doi = {10.4230/LIPIcs.MFCS.2021.84}, annote = {Keywords: Cayley graphs, counting complexity, expander graphs, fine-grained complexity, parameterized complexity} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Marc Roth, Johannes Schmitt, and Philip Wellnitz. Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 108:1-108:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{roth_et_al:LIPIcs.ICALP.2021.108, author = {Roth, Marc and Schmitt, Johannes and Wellnitz, Philip}, title = {{Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {108:1--108: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.108}, URN = {urn:nbn:de:0030-drops-141778}, doi = {10.4230/LIPIcs.ICALP.2021.108}, annote = {Keywords: Counting complexity, parameterized complexity, Tutte polynomial} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dorfler_et_al:LIPIcs.MFCS.2019.26, author = {D\"{o}rfler, Julian and Roth, Marc and Schmitt, Johannes and Wellnitz, Philip}, title = {{Counting Induced Subgraphs: An Algebraic Approach to #W\lbrack1\rbrack-hardness}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {26:1--26:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.26}, URN = {urn:nbn:de:0030-drops-109703}, doi = {10.4230/LIPIcs.MFCS.2019.26}, annote = {Keywords: counting complexity, edge-transitive graphs, graph homomorphisms, induced subgraphs, parameterized complexity} }
Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Marc Roth and Johannes Schmitt. Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{roth_et_al:LIPIcs.IPEC.2018.24, author = {Roth, Marc and Schmitt, Johannes}, title = {{Counting Induced Subgraphs: A Topological Approach to #W\lbrack1\rbrack-hardness}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.24}, URN = {urn:nbn:de:0030-drops-102255}, doi = {10.4230/LIPIcs.IPEC.2018.24}, annote = {Keywords: counting complexity, Euler characteristic, homomorphisms, parameterized complexity, simplicial complexes} }
Feedback for Dagstuhl Publishing