LIPIcs, Volume 159
AofA 2020, June 15-19, 2020, Klagenfurt, Austria (Virtual Conference)
Editors: Michael Drmota and Clemens Heuberger
Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Gabriel Berzunza Ojeda, Cecilia Holmgren, and Svante Janson. Fringe Trees for Random Trees with Given Vertex Degrees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{berzunzaojeda_et_al:LIPIcs.AofA.2024.1, author = {Berzunza Ojeda, Gabriel and Holmgren, Cecilia and Janson, Svante}, title = {{Fringe Trees for Random Trees with Given Vertex Degrees}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {1:1--1:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.1}, URN = {urn:nbn:de:0030-drops-204369}, doi = {10.4230/LIPIcs.AofA.2024.1}, annote = {Keywords: Conditioned Galton-Watson trees, fringe trees, simply generated trees, uniformly random trees with given vertex degrees} }
Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Cyril Banderier, Markus Kuba, Stephan Wagner, and Michael Wallner. Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{banderier_et_al:LIPIcs.AofA.2024.7, author = {Banderier, Cyril and Kuba, Markus and Wagner, Stephan and Wallner, Michael}, title = {{Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.7}, URN = {urn:nbn:de:0030-drops-204427}, doi = {10.4230/LIPIcs.AofA.2024.7}, annote = {Keywords: Composition schemes, q-enumeration, generating functions, Gibbs distribution, phase transitions, limit laws, Mittag-Leffler distribution, chi distribution, Boltzmann distribution} }
Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Jasper Ischebeck and Ralph Neininger. On Fluctuations of Complexity Measures for the FIND Algorithm. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ischebeck_et_al:LIPIcs.AofA.2024.9, author = {Ischebeck, Jasper and Neininger, Ralph}, title = {{On Fluctuations of Complexity Measures for the FIND Algorithm}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {9:1--9:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.9}, URN = {urn:nbn:de:0030-drops-204440}, doi = {10.4230/LIPIcs.AofA.2024.9}, annote = {Keywords: FIND, Quickselect, rank selection, probabilistic analysis of algorithms, weak convergence, functional limit theorem} }
Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Fabian Burghart and Stephan Wagner. A Bijection for the Evolution of B-Trees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{burghart_et_al:LIPIcs.AofA.2024.10, author = {Burghart, Fabian and Wagner, Stephan}, title = {{A Bijection for the Evolution of B-Trees}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.10}, URN = {urn:nbn:de:0030-drops-204451}, doi = {10.4230/LIPIcs.AofA.2024.10}, annote = {Keywords: B-trees, histories, increasing trees, bijection, asymptotic enumeration, tree statistics} }
Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Stephan Wagner. On the Number of Distinct Fringe Subtrees in Binary Search Trees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 13:1-13:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{wagner:LIPIcs.AofA.2024.13, author = {Wagner, Stephan}, title = {{On the Number of Distinct Fringe Subtrees in Binary Search Trees}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {13:1--13:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.13}, URN = {urn:nbn:de:0030-drops-204482}, doi = {10.4230/LIPIcs.AofA.2024.13}, annote = {Keywords: Fringe subtrees, binary search trees, tree compression, minimal DAG, asymptotics} }
Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Michael Drmota and Eva-Maria Hainzl. Universal Properties of Catalytic Variable Equations. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{drmota_et_al:LIPIcs.AofA.2022.7, author = {Drmota, Michael and Hainzl, Eva-Maria}, title = {{Universal Properties of Catalytic Variable Equations}}, booktitle = {33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)}, pages = {7:1--7:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-230-3}, ISSN = {1868-8969}, year = {2022}, volume = {225}, editor = {Ward, Mark Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.7}, URN = {urn:nbn:de:0030-drops-160930}, doi = {10.4230/LIPIcs.AofA.2022.7}, annote = {Keywords: catalytic equation, singular expansion, univeral asymptotics} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 1-402, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@Proceedings{drmota_et_al:LIPIcs.AofA.2020, title = {{LIPIcs, Volume 159, AofA 2020, Complete Volume}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {1--402}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020}, URN = {urn:nbn:de:0030-drops-120296}, doi = {10.4230/LIPIcs.AofA.2020}, annote = {Keywords: LIPIcs, Volume 159, AofA 2020, Complete Volume} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{drmota_et_al:LIPIcs.AofA.2020.0, author = {Drmota, Michael and Heuberger, Clemens}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {0:i--0:xii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.0}, URN = {urn:nbn:de:0030-drops-120309}, doi = {10.4230/LIPIcs.AofA.2020.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Andrei Asinowski and Cyril Banderier. On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{asinowski_et_al:LIPIcs.AofA.2020.1, author = {Asinowski, Andrei and Banderier, Cyril}, title = {{On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {1:1--1:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.1}, URN = {urn:nbn:de:0030-drops-120317}, doi = {10.4230/LIPIcs.AofA.2020.1}, annote = {Keywords: Lattice path, Dyck path, Motzkin path, generating function, algebraic function, kernel method, context-free grammar, multivariate Gaussian distribution} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Cyril Banderier, Marie-Louise Lackner, and Michael Wallner. Latticepathology and Symmetric Functions (Extended Abstract). In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{banderier_et_al:LIPIcs.AofA.2020.2, author = {Banderier, Cyril and Lackner, Marie-Louise and Wallner, Michael}, title = {{Latticepathology and Symmetric Functions (Extended Abstract)}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {2:1--2:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.2}, URN = {urn:nbn:de:0030-drops-120329}, doi = {10.4230/LIPIcs.AofA.2020.2}, annote = {Keywords: Lattice path, generating function, symmetric function, algebraic function, kernel method, context-free grammar, Sparre Andersen formula, Spitzer’s identity, Wiener - Hopf factorization} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Frédérique Bassino, Tsinjo Rakotoarimalala, and Andrea Sportiello. The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bassino_et_al:LIPIcs.AofA.2020.3, author = {Bassino, Fr\'{e}d\'{e}rique and Rakotoarimalala, Tsinjo and Sportiello, Andrea}, title = {{The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.3}, URN = {urn:nbn:de:0030-drops-120336}, doi = {10.4230/LIPIcs.AofA.2020.3}, annote = {Keywords: Average-case analysis of algorithms, String Pattern Matching, Computational Complexity bounds} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Valérie Berthé, Eda Cesaratto, Frédéric Paccaut, Pablo Rotondo, Martín D. Safe, and Brigitte Vallée. Two Arithmetical Sources and Their Associated Tries. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{berthe_et_al:LIPIcs.AofA.2020.4, author = {Berth\'{e}, Val\'{e}rie and Cesaratto, Eda and Paccaut, Fr\'{e}d\'{e}ric and Rotondo, Pablo and Safe, Mart{\'\i}n D. and Vall\'{e}e, Brigitte}, title = {{Two Arithmetical Sources and Their Associated Tries}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.4}, URN = {urn:nbn:de:0030-drops-120345}, doi = {10.4230/LIPIcs.AofA.2020.4}, annote = {Keywords: Combinatorics of words, Information Theory, Probabilistic analysis, Analytic combinatorics, Dirichlet generating functions, Sources, Partitions, Trie structure, Continued fraction expansion, Farey map, Sturm words, Transfer operator} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Gabriel Berzunza, Xing Shi Cai, and Cecilia Holmgren. The k-Cut Model in Conditioned Galton-Watson Trees. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{berzunza_et_al:LIPIcs.AofA.2020.5, author = {Berzunza, Gabriel and Cai, Xing Shi and Holmgren, Cecilia}, title = {{The k-Cut Model in Conditioned Galton-Watson Trees}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {5:1--5:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.5}, URN = {urn:nbn:de:0030-drops-120352}, doi = {10.4230/LIPIcs.AofA.2020.5}, annote = {Keywords: k-cut, cutting, conditioned Galton-Watson trees} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Gabriel Berzunza and Cecilia Holmgren. Largest Clusters for Supercritical Percolation on Split Trees. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{berzunza_et_al:LIPIcs.AofA.2020.6, author = {Berzunza, Gabriel and Holmgren, Cecilia}, title = {{Largest Clusters for Supercritical Percolation on Split Trees}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {6:1--6:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.6}, URN = {urn:nbn:de:0030-drops-120361}, doi = {10.4230/LIPIcs.AofA.2020.6}, annote = {Keywords: Split trees, random trees, supercritical bond-percolation, cluster size, Poisson measures} }