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.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.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.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 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Jan Kratochvíl, Tomáš Masařík, and Jana Novotná. U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kratochvil_et_al:LIPIcs.MFCS.2020.57, author = {Kratochv{\'\i}l, Jan and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana}, title = {{U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {57:1--57:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.57}, URN = {urn:nbn:de:0030-drops-127247}, doi = {10.4230/LIPIcs.MFCS.2020.57}, annote = {Keywords: Interval Graphs, Mixed Unit Interval Graphs, MaxCut Problem, Clique Width, Subexponential Algorithm, Bubble Model} }
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.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} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Martin Balko, Vít Jelínek, Pavel Valtr, and Bartosz Walczak. On the Beer Index of Convexity and Its Variants. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 406-420, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{balko_et_al:LIPIcs.SOCG.2015.406, author = {Balko, Martin and Jel{\'\i}nek, V{\'\i}t and Valtr, Pavel and Walczak, Bartosz}, title = {{On the Beer Index of Convexity and Its Variants}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {406--420}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.406}, URN = {urn:nbn:de:0030-drops-51229}, doi = {10.4230/LIPIcs.SOCG.2015.406}, annote = {Keywords: Beer index of convexity, convexity ratio, convexity measure, visibility} }
Feedback for Dagstuhl Publishing