Critical random graphs and the structure of a minimum spanning tree

DOI10.1002/rsa.20241zbMath1214.05154OpenAlexW3083377090MaRDI QIDQ3055778

Nicolas Broutin, Louigi Addario-Berry, Bruce A. Reed

Publication date: 9 November 2010

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20241

zbMATH Keywords

random walksrandom graphsminimum spanning treesrandom trees

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Related Items (10)

Partition Functions of Discrete Coalescents: From Cayley’s Formula to Frieze’s ζ(3) Limit Theorem ⋮ GHS algorithm on a graph with random weights ⋮ The continuum limit of critical random graphs ⋮ Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks ⋮ The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs ⋮ Continuum limit of critical inhomogeneous random graphs ⋮ Aggregation models with limited choice and the multiplicative coalescent ⋮ Geometry of the minimal spanning tree of a random 3-regular graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On random minimum length spanning trees
• On the value of a random minimum spanning tree problem
• Branching processes in the analysis of the heights of trees
• The average height of binary trees and other simple trees
• Brownian excursions, critical random graphs and the multiplicative coalescent
• On the largest component of the random graph at a nearcritical stage
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• The Evolution of Random Graphs
• A random tree model associated with random graphs
• Component behavior near the critical point of the random graph process
• Note on the heights of random recursive trees and random m‐ary search trees
• The Structure of a Random Graph at the Point of the Phase Transition
• The Distribution of Heights of Binary Trees and Other Simple Trees
• On the History of the Minimum Spanning Tree Problem
• The birth of the giant component
• A Point Process Describing the Component Sizes in the Critical Window of the Random Graph Evolution
• On the height of trees
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• The diameter of sparse random graphs

This page was built for publication: Critical random graphs and the structure of a minimum spanning tree