Document

**Published in:** LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

We present an analysis of the depth-first search algorithm in a random digraph model with geometric outdegree distribution. We give also some extensions to general outdegree distributions. This problem posed by Donald Knuth in his next to appear volume of The Art of Computer Programming gives interesting insight in one of the most elegant and efficient algorithm for graph analysis due to Tarjan.

Philippe Jacquet and Svante Janson. Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution. 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. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jacquet_et_al:LIPIcs.AofA.2022.11, author = {Jacquet, Philippe and Janson, Svante}, title = {{Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution}}, booktitle = {33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)}, pages = {11:1--11: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.11}, URN = {urn:nbn:de:0030-drops-160978}, doi = {10.4230/LIPIcs.AofA.2022.11}, annote = {Keywords: Combinatorics, Depth-First Search, Random Digraphs} }

Document

**Published in:** LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

We study here the so called subsequence pattern matching also known as hidden pattern matching in which one searches for a given pattern w of length m as a subsequence in a random text of length n. The quantity of interest is the number of occurrences of w as a subsequence (i.e., occurring in not necessarily consecutive text locations). This problem finds many applications from intrusion detection, to trace reconstruction, to deletion channel, and to DNA-based storage systems. In all of these applications, the pattern w is of variable length. To the best of our knowledge this problem was only tackled for a fixed length m=O(1) [P. Flajolet et al., 2006]. In our main result Theorem 5 we prove that for m=o(n^{1/3}) the number of subsequence occurrences is normally distributed. In addition, in Theorem 6 we show that under some constraints on the structure of w the asymptotic normality can be extended to m=o(√n). For a special pattern w consisting of the same symbol, we indicate that for m=o(n) the distribution of number of subsequences is either asymptotically normal or asymptotically log normal. We conjecture that this dichotomy is true for all patterns. We use Hoeffding’s projection method for U-statistics to prove our findings.

Svante Janson and Wojciech Szpankowski. Hidden Words Statistics for Large Patterns. 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. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{janson_et_al:LIPIcs.AofA.2020.17, author = {Janson, Svante and Szpankowski, Wojciech}, title = {{Hidden Words Statistics for Large Patterns}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {17:1--17: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.17}, URN = {urn:nbn:de:0030-drops-120476}, doi = {10.4230/LIPIcs.AofA.2020.17}, annote = {Keywords: Hidden pattern matching, subsequences, probability, U-statistics, projection method} }

Document

RANDOM

**Published in:** LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

In a complete graph K_n with edge weights drawn independently from a uniform distribution U(0,1) (or alternatively an exponential distribution Exp(1)), let T_1 be the MST (the spanning tree of minimum weight) and let T_k be the MST after deletion of the edges of all previous trees T_i, i<k. We show that each tree’s weight w(T_k) converges in probability to a constant gamma_k with 2k-2 sqrt k < gamma_k < 2k+2 sqrt k, and we conjecture that gamma_k = 2k-1+o(1). The problem is distinct from that of [Alan Frieze and Tony Johansson, 2018], finding k MSTs of combined minimum weight, and the combined cost for two trees in their problem is, asymptotically, strictly smaller than our gamma_1+gamma_2.
Our results also hold (and mostly are derived) in a multigraph model where edge weights for each vertex pair follow a Poisson process; here we additionally have E(w(T_k)) -> gamma_k. Thinking of an edge of weight w as arriving at time t=n w, Kruskal’s algorithm defines forests F_k(t), each initially empty and eventually equal to T_k, with each arriving edge added to the first F_k(t) where it does not create a cycle. Using tools of inhomogeneous random graphs we obtain structural results including that C_1(F_k(t))/n, the fraction of vertices in the largest component of F_k(t), converges in probability to a function rho_k(t), uniformly for all t, and that a giant component appears in F_k(t) at a time t=sigma_k. We conjecture that the functions rho_k tend to time translations of a single function, rho_k(2k+x) -> rho_infty(x) as k -> infty, uniformly in x in R.
Simulations and numerical computations give estimated values of gamma_k for small k, and support the conjectures stated above.

Svante Janson and Gregory B. Sorkin. Successive Minimum Spanning Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{janson_et_al:LIPIcs.APPROX-RANDOM.2019.60, author = {Janson, Svante and Sorkin, Gregory B.}, title = {{Successive Minimum Spanning Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {60:1--60:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.60}, URN = {urn:nbn:de:0030-drops-112759}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.60}, annote = {Keywords: miminum spanning tree, second-cheapest structure, inhomogeneous random graph, optimization in random structures, discrete probability, multi-type branching process, functional fixed point, robust optimization, Kruskal’s algorithm} }

Document

Keynote Speakers

**Published in:** LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Consider a random permutation drawn from the set of permutations of length n that avoid a given set of one or several patterns of length 3. We show that the number of occurrences of another pattern has a limit distribution, after suitable scaling. In several cases, the limit is normal, as it is in the case of unrestricted random permutations; in other cases the limit is a non-normal distribution, depending on the studied pattern. In the case when a single pattern of length 3 is forbidden, the limit distributions can be expressed in terms of a Brownian excursion.
The analysis is made case by case; unfortunately, no general method is known, and no general pattern emerges from the results.

Svante Janson. Patterns in Random Permutations Avoiding Some Other Patterns (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{janson:LIPIcs.AofA.2018.6, author = {Janson, Svante}, title = {{Patterns in Random Permutations Avoiding Some Other Patterns}}, booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)}, pages = {6:1--6:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-078-1}, ISSN = {1868-8969}, year = {2018}, volume = {110}, editor = {Fill, James Allen and 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.2018.6}, URN = {urn:nbn:de:0030-drops-88996}, doi = {10.4230/LIPIcs.AofA.2018.6}, annote = {Keywords: Random permutations, patterns, forbidden patterns, limit in distribution, U-statistics} }

Document

**Published in:** LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

We study I(T), the number of inversions in a tree T with its vertices labeled uniformly at random. We first show that the cumulants of I(T) have explicit formulas. Then we consider X_n, the normalized version of I(T_n), for a sequence of trees T_n. For fixed T_n's, we prove a sufficient condition for X_n to converge in distribution. For T_n being split trees [Devroye, 1999], we show that X_n converges to the unique solution of a distributional equation. Finally, when T_n's are conditional Galton-Watson trees, we show that X_n converges to a random variable defined in terms of Brownian excursions. Our results generalize and extend previous work by Panholzer and Seitz [Panholzer and Seitz, 2012].

Xing Shi Cai, Cecilia Holmgren, Svante Janson, Tony Johansson, and Fiona Skerman. Inversions in Split Trees and Conditional Galton-Watson Trees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 15:1-15:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.AofA.2018.15, author = {Cai, Xing Shi and Holmgren, Cecilia and Janson, Svante and Johansson, Tony and Skerman, Fiona}, title = {{Inversions in Split Trees and Conditional Galton-Watson Trees}}, booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)}, pages = {15:1--15:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-078-1}, ISSN = {1868-8969}, year = {2018}, volume = {110}, editor = {Fill, James Allen and 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.2018.15}, URN = {urn:nbn:de:0030-drops-89085}, doi = {10.4230/LIPIcs.AofA.2018.15}, annote = {Keywords: inversions, random trees, split trees, Galton-Watson trees, permutation, cumulant} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail