Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Vít Jelínek, Michal Opler, and Jakub Pekárek. Long Paths Make Pattern-Counting Hard, and Deep Trees Make It Harder. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{jelinek_et_al:LIPIcs.IPEC.2021.22, author = {Jel{\'\i}nek, V{\'\i}t and Opler, Michal and Pek\'{a}rek, Jakub}, title = {{Long Paths Make Pattern-Counting Hard, and Deep Trees Make It Harder}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {22:1--22:17}, 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.22}, URN = {urn:nbn:de:0030-drops-154050}, doi = {10.4230/LIPIcs.IPEC.2021.22}, annote = {Keywords: Permutation pattern matching, subexponential algorithm, conditional lower bounds, tree-width} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Vít Jelínek, Michal Opler, and Jakub Pekárek. Griddings of Permutations and Hardness of Pattern Matching. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 65:1-65:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{jelinek_et_al:LIPIcs.MFCS.2021.65, author = {Jel{\'\i}nek, V{\'\i}t and Opler, Michal and Pek\'{a}rek, Jakub}, title = {{Griddings of Permutations and Hardness of Pattern Matching}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {65:1--65:22}, 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.65}, URN = {urn:nbn:de:0030-drops-145050}, doi = {10.4230/LIPIcs.MFCS.2021.65}, annote = {Keywords: Permutation, pattern matching, NP-hardness} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Vít Jelínek, Michal Opler, and Jakub Pekárek. A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 52:1-52:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{jelinek_et_al:LIPIcs.MFCS.2020.52, author = {Jel{\'\i}nek, V{\'\i}t and Opler, Michal and Pek\'{a}rek, Jakub}, title = {{A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {52:1--52:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.52}, URN = {urn:nbn:de:0030-drops-127186}, doi = {10.4230/LIPIcs.MFCS.2020.52}, annote = {Keywords: permutations, pattern matching, grid classes} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Vít Jelínek, Michal Opler, and Pavel Valtr. Generalized Coloring of Permutations. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{jelinek_et_al:LIPIcs.ESA.2018.50, author = {Jel{\'\i}nek, V{\'\i}t and Opler, Michal and Valtr, Pavel}, title = {{Generalized Coloring of Permutations}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {50:1--50:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah 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.2018.50}, URN = {urn:nbn:de:0030-drops-95137}, doi = {10.4230/LIPIcs.ESA.2018.50}, annote = {Keywords: Permutations, merge, generalized coloring} }
Feedback for Dagstuhl Publishing