5 Search Results for "Johansson, Tony"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.60
Successive Minimum Spanning Trees

Authors: Svante Janson and Gregory B. Sorkin

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.45
The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree

Authors: Tony Johansson

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We consider a random walk process, introduced by Orenshtein and Shinkar [Tal Orenshtein and Igor Shinkar, 2014], which prefers to visit previously unvisited edges, on the random r-regular graph G_r for any odd r >= 3. We show that this random walk process has asymptotic vertex and edge cover times 1/(r-2)n log n and r/(2(r-2))n log n, respectively, generalizing the result from [Cooper et al., to appear] from r = 3 to any larger odd r. This completes the study of the vertex cover time for fixed r >= 3, with [Petra Berenbrink et al., 2015] having previously shown that G_r has vertex cover time asymptotic to rn/2 when r >= 4 is even.
Cite as

Tony Johansson. The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{johansson:LIPIcs.APPROX-RANDOM.2018.45,
  author =	{Johansson, Tony},
  title =	{{The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.45},
  URN =		{urn:nbn:de:0030-drops-94494},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.45},
  annote =	{Keywords: Random walk, random regular graph, cover time}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.9
Permutations in Binary Trees and Split Trees

Authors: Michael Albert, Cecilia Holmgren, Tony Johansson, and Fiona Skerman

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

Abstract
We investigate the number of permutations that occur in random node labellings of trees. This is a generalisation of the number of subpermutations occuring in a random permutation. It also generalises some recent results on the number of inversions in randomly labelled trees [Cai et al., 2017]. We consider complete binary trees as well as random split trees a large class of random trees of logarithmic height introduced by Devroye [Devroye, 1998]. Split trees consist of nodes (bags) which can contain balls and are generated by a random trickle down process of balls through the nodes. For complete binary trees we show that asymptotically the cumulants of the number of occurrences of a fixed permutation in the random node labelling have explicit formulas. Our other main theorem is to show that for a random split tree with high probability the cumulants of the number of occurrences are asymptotically an explicit parameter of the split tree. For the proof of the second theorem we show some results on the number of embeddings of digraphs into split trees which may be of independent interest.
Cite as

Michael Albert, Cecilia Holmgren, Tony Johansson, and Fiona Skerman. Permutations in Binary Trees and Split 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. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{albert_et_al:LIPIcs.AofA.2018.9,
  author =	{Albert, Michael and Holmgren, Cecilia and Johansson, Tony and Skerman, Fiona},
  title =	{{Permutations in Binary Trees and Split Trees}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-89025},
  doi =		{10.4230/LIPIcs.AofA.2018.9},
  annote =	{Keywords: random trees, split trees, permutations, inversions, cumulant}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.15
Inversions in Split Trees and Conditional Galton-Watson Trees

Authors: Xing Shi Cai, Cecilia Holmgren, Svante Janson, Tony Johansson, and Fiona Skerman

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

Abstract
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].
Cite as

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}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.16
The Cover Time of a Biased Random Walk on a Random Cubic Graph

Authors: Colin Cooper, Alan Frieze, and Tony Johansson

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

Abstract
We study a random walk that prefers to use unvisited edges in the context of random cubic graphs, i.e., graphs chosen uniformly at random from the set of 3-regular graphs. We establish asymptotically correct estimates for the vertex and edge cover times, these being n log n and 3/2 n log n respectively.
Cite as

Colin Cooper, Alan Frieze, and Tony Johansson. The Cover Time of a Biased Random Walk on a Random Cubic Graph. 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. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.AofA.2018.16,
  author =	{Cooper, Colin and Frieze, Alan and Johansson, Tony},
  title =	{{The Cover Time of a Biased Random Walk on a Random Cubic Graph}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{16:1--16: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.16},
  URN =		{urn:nbn:de:0030-drops-89097},
  doi =		{10.4230/LIPIcs.AofA.2018.16},
  annote =	{Keywords: Random walk, random regular graph, cover time}
}
  • Refine by Author
  • 4 Johansson, Tony
  • 2 Holmgren, Cecilia
  • 2 Janson, Svante
  • 2 Skerman, Fiona
  • 1 Albert, Michael
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Random walk
  • 2 cover time
  • 2 cumulant
  • 2 inversions
  • 2 random regular graph
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 4 2018
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact