scientific article; zbMATH DE number 7650127

DOI10.4230/LIPICS.APPROX-RANDOM.2019.60MaRDI QIDQ5875520zbMATH OpenFDO

Authors Svante Janson, Gregory B. Sorkin

Publication date 3 February 2023

Full work available at URL https://arxiv.org/abs/1906.01533

zbMATH Keywords

discrete probabilityinhomogeneous random graphoptimization in random structuressecond-cheapest structuremiminum spanning treemulti-type bra

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 3950585 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 1962848 (Why is no real title available?)
• A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
• Algorithmic Game Theory
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Average-Case Analyses of Vickrey Costs
• Frugal path mechanisms
• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• On the length of a random minimum spanning tree
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On the value of a random minimum spanning tree problem
• Successive shortest paths in complete graphs with random edge weights
• The birth of the giant component
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• The phase transition in inhomogeneous random graphs

Cited in

(2)

• Note on the structure of Kruskal's algorithm
• Successive minimum spanning trees

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875520)