On the value of a random minimum spanning tree problem

Alan Frieze

Type: Article

Publication Date: 1985-01-01

Citations: 239

DOI: https://doi.org/10.1016/0166-218x(85)90058-7

View Publication

Locations

Discrete Applied Mathematics - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	On the Length of a Random Minimum Spanning Tree	2015	Colin Cooper Alan Frieze Nate Ince Svante Janson Joel Spencer
+	SPANNING TREE PROBLEM	1985	Alan Frieze
+ PDF Chat	A randomly weighted minimum spanning tree with a random cost constraint	2019	Alan Frieze Tomasz Tkocz
+	The expected value of random minimal length spanning tree of a complete graph	2005	David Gamarnik
+	A randomly weighted minimum spanning tree with a random cost constraint	2019	Alan Frieze Tomasz Tkocz
+ PDF Chat	A Randomly Weighted Minimum Spanning Tree with a Random Cost Constraint	2021	Alan Frieze Tomasz Tkocz
+	A randomly weighted minimum spanning tree with a random cost constraint	2020	Alan Frieze Tomasz Tkocz
+	On the Value of a Random Minimum Weight Steiner Tree	2004	Béla Bollobás David Gamarnik Oliver Riordan Benny Sudakov
+ PDF Chat	On the Random Minimum Spanning Subgraph Problem for Hypergraphs	2024	Nikita Zvonkov
+ PDF Chat	The Lower Tail of the Random Minimum Spanning Tree	2007	Abraham D. Flaxman
+ PDF Chat	On a random directed spanning tree	2004	Abhay G. Bhatt R. Roy
+ PDF Chat	On a random directed spanning tree	2004	Abhay G. Bhatt R. Roy
+	A randomly weighted minimum arborescence with a random cost constraint	2019	Alan Frieze Tomasz Tkocz
+	A randomly weighted minimum arborescence with a random cost constraint	2019	Alan Frieze Tomasz Tkocz
+	On finding a minimum spanning tree in a network with random weights	2000	Colin McDiarmid Theodore M. Johnson Harold S. Stone
+ PDF Chat	On minimum spanning trees for random Euclidean bipartite graphs	2023	Mario Correddu Dario Trevisan
+ PDF Chat	A Note on Random Minimum Length Spanning Trees	2000	Alan Frieze Miklós Ruszinkó Luboš Thoma
+	Evaluation of Janson’s constant for the variance in the random minimum spanning tree problem	2005	Johan Wästlund
+	The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights	2020	Othmane Safsafi
+ PDF Chat	The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights	2023	Othmane Safsafi

Works That Cite This (173)

Action	Title	Year	Authors
+ PDF Chat	Cross-multiplicative coalescent processes and applications	2020	Yevgeniy Kovchegov Peter T. Otto Anatoly Yambartsev
+	Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes	2024	Shankar Bhamidi Sanchayan Sen
+ PDF Chat	A proof of Parisi’s conjecture on the random assignment problem	2003	Svante Linusson Johan Wästlund
+ PDF Chat	Noise sensitivity of the minimum spanning tree of the complete graph	2024	Omer Israeli Yuval Peled
+ PDF Chat	Percolation of averages in the stochastic mean field model: the near-supercritical regime	2015	Jian Ding Subhajit Goswami
+ PDF Chat	Edge flows in the complete random‐lengths network	2010	David Aldous Shankar Bhamidi
+ PDF Chat	Minimal Spanning Trees for Graphs with Random Edge Lengths	2002	J. Michael Steele
+	Martingale Inequalities, Interpolation and NP-Complete Problems	1989	Wansoo T. Rhee Michel Talagrand
+	Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points	2012	Lingxiao Huang Jian Li
+	Polynomial representation for the expected length of minimal spanning trees	2015	Jared Nishikawa Peter T. Otto Colin Starr

Works Cited by This (3)

Action	Title	Year	Authors
+	On the connectivity of randomm-orientable graphs and digraphs	1982	T. I. Fenner Alan Frieze
+ PDF Chat	Optimization Problems on Graphs with Independent Random Edge Weights	1981	George S. Lueker
+ PDF Chat	On the shortest spanning subtree of a graph and the traveling salesman problem	1956	Joseph B. Kruskal