Successive minimum spanning trees
DOI10.1002/rsa.21047zbMath1522.05036OpenAlexW2978544150MaRDI QIDQ6074707
Gregory B. Sorkin, Svante Janson
Publication date: 12 October 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11275/
robust optimizationminimum spanning treemulti-type branching processdiscrete probabilityinhomogeneous random graphKruskal's algorithmoptimization in random structuressecond-cheapest structurefunctional fixed point
Trees (05C05) Combinatorial probability (60C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Signed and weighted graphs (05C22)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Susceptibility in inhomogeneous random graphs
- On random minimum length spanning trees
- An easy proof of the \(\zeta (2)\) limit in the random assignment problem
- On the value of a random minimum spanning tree problem
- On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees
- Sudden emergence of a giant \(k\)-core in a random graph
- Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
- Frugal path mechanisms
- Successive shortest paths in complete graphs with random edge weights
- A simple solution to the k‐core problem
- Average-Case Analyses of Vickrey Costs
- On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
- Paths in graphs
- The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
- The birth of the giant component
- The phase transition in inhomogeneous random graphs
- On the Length of a Random Minimum Spanning Tree
- Algorithmic Game Theory
- Decomposition of Finite Graphs Into Forests
- Probability: A Graduate Course
- The cut metric, random graphs, and branching processes
This page was built for publication: Successive minimum spanning trees
