文章基本信息

标题：Successive Minimum Spanning Trees
本地全文：下载
作者：Svante Janson ; Gregory B. Sorkin
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：145
页码：1-16
DOI：10.4230/LIPIcs.APPROX-RANDOM.2019.60
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 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.
关键词：miminum spanning tree; second-cheapest structure; inhomogeneous random graph; optimization in random structures; discrete probability; multi-type bra