Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
Panagiotis Charalampopoulos, Bartłomiej Dudek, Paweł Gawrychowski, and Karol Pokorski. Optimal Near-Linear Space Heaviest Induced Ancestors. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{charalampopoulos_et_al:LIPIcs.CPM.2023.8, author = {Charalampopoulos, Panagiotis and Dudek, Bart{\l}omiej and Gawrychowski, Pawe{\l} and Pokorski, Karol}, title = {{Optimal Near-Linear Space Heaviest Induced Ancestors}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {8:1--8:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-276-1}, ISSN = {1868-8969}, year = {2023}, volume = {259}, editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.8}, URN = {urn:nbn:de:0030-drops-179624}, doi = {10.4230/LIPIcs.CPM.2023.8}, annote = {Keywords: data structures, string algorithms, fractional cascading} }
Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Talley Amir, James Aspnes, and John Lazarsfeld. Approximate Majority with Catalytic Inputs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{amir_et_al:LIPIcs.OPODIS.2020.19, author = {Amir, Talley and Aspnes, James and Lazarsfeld, John}, title = {{Approximate Majority with Catalytic Inputs}}, booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)}, pages = {19:1--19:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-176-4}, ISSN = {1868-8969}, year = {2021}, volume = {184}, editor = {Bramas, Quentin and Oshman, Rotem and Romano, Paolo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.19}, URN = {urn:nbn:de:0030-drops-135040}, doi = {10.4230/LIPIcs.OPODIS.2020.19}, annote = {Keywords: population protocols, approximate majority, catalysts, leaks, lower bound} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Bartłomiej Dudek and Paweł Gawrychowski. Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dudek_et_al:LIPIcs.ISAAC.2020.23, author = {Dudek, Bart{\l}omiej and Gawrychowski, Pawe{\l}}, title = {{Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {23:1--23:18}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.23}, URN = {urn:nbn:de:0030-drops-133678}, doi = {10.4230/LIPIcs.ISAAC.2020.23}, annote = {Keywords: Permutations, pattern avoidance, counting cycles} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Bartłomiej Dudek, Paweł Gawrychowski, and Tatiana Starikovskaya. Generalised Pattern Matching Revisited. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dudek_et_al:LIPIcs.STACS.2020.18, author = {Dudek, Bart{\l}omiej and Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, title = {{Generalised Pattern Matching Revisited}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {18:1--18:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.18}, URN = {urn:nbn:de:0030-drops-118798}, doi = {10.4230/LIPIcs.STACS.2020.18}, annote = {Keywords: pattern matching, superimposed codes, conditional lower bounds} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Bartlomiej Dudek and Pawel Gawrychowski. Edit Distance between Unrooted Trees in Cubic Time. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dudek_et_al:LIPIcs.ICALP.2018.45, author = {Dudek, Bartlomiej and Gawrychowski, Pawel}, title = {{Edit Distance between Unrooted Trees in Cubic Time}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {45:1--45:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.45}, URN = {urn:nbn:de:0030-drops-90492}, doi = {10.4230/LIPIcs.ICALP.2018.45}, annote = {Keywords: tree edit distance, dynamic programming, heavy light decomposition} }
Published in: LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Bartlomiej Dudek and Pawel Gawrychowski. Slowing Down Top Trees for Better Worst-Case Compression. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 16:1-16:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dudek_et_al:LIPIcs.CPM.2018.16, author = {Dudek, Bartlomiej and Gawrychowski, Pawel}, title = {{Slowing Down Top Trees for Better Worst-Case Compression}}, booktitle = {29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)}, pages = {16:1--16:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-074-3}, ISSN = {1868-8969}, year = {2018}, volume = {105}, editor = {Navarro, Gonzalo and Sankoff, David and Zhu, Binhai}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.16}, URN = {urn:nbn:de:0030-drops-86920}, doi = {10.4230/LIPIcs.CPM.2018.16}, annote = {Keywords: top trees, compression, tree grammars} }
Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Bartlomiej Dudek, Pawel Gawrychowski, and Piotr Ostropolski-Nalewaja. A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{dudek_et_al:LIPIcs.CPM.2017.10, author = {Dudek, Bartlomiej and Gawrychowski, Pawel and Ostropolski-Nalewaja, Piotr}, title = {{A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem}}, booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)}, pages = {10:1--10:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-039-2}, ISSN = {1868-8969}, year = {2017}, volume = {78}, editor = {K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.10}, URN = {urn:nbn:de:0030-drops-73458}, doi = {10.4230/LIPIcs.CPM.2017.10}, annote = {Keywords: approximation scheme, minimum common string partition, local search} }
Feedback for Dagstuhl Publishing