A randomly weighted minimum spanning tree with a random cost constraint

DOI10.37236/9445zbMath1456.05146arXiv1905.01229OpenAlexW3130835883MaRDI QIDQ2223477

Tomasz Tkocz, Alan M. Frieze

Publication date: 29 January 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic value of the optimum weightsymmetric logarithmic Sobolev inequality

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Signed and weighted graphs (05C22)

Related Items (3)

A Randomly Weighted Minimum Arborescence with a Random Cost Constraint ⋮ Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects ⋮ Typical values of extremal-weight combinatorial structures with independent symmetric weights

Cites Work

• Unnamed Item
• Unnamed Item
• On random minimum length spanning trees
• On the value of a random minimum spanning tree problem
• Random minimum length spanning trees in regular graphs
• Concentration inequalities using the entropy method
• A note on random minimum length spanning trees
• A note on log-concave random graphs
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• On the Difference of Expected Lengths of Minimum Spanning Trees
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• The constrained minimum spanning tree problem
• On the Length of a Random Minimum Spanning Tree

This page was built for publication: A randomly weighted minimum spanning tree with a random cost constraint