A randomly weighted minimum spanning tree with a random cost constraint

DOI10.37236/9445MaRDI QIDQ2223477zbMATH OpenOpenAlexFDO

Authors Tomasz Tkocz, Alan Frieze

Publication date 29 January 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

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)

Abstract: We study the minimum spanning tree problem on the complete graph $K_n$ where an edge $e$ has a weight $W_e$ and a cost $C_e$, each of which is an independent copy of the random variable $U^{g}amma$ where $gammaleq1$ and $U$ is the uniform $[0,1]$ random variable. There is also a constraint that the spanning tree $T$ must satisfy $C(T)leq{c}_0$. We establish, for a range of values for $c_0,gamma$, the asymptotic value of the optimum weight via the consideration of a dual problem.

Recommendations

• A randomly weighted minimum arborescence with a random cost constraint
• Minimum-weight combinatorial structures under random cost-constraints
• On the value of a random minimum spanning tree problem
• The minimum weight spanning tree with constraints
• On random minimum length spanning trees

Cites work

• scientific article; zbMATH DE number 1123759 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• A note on log-concave random graphs
• A note on random minimum length spanning trees
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• Concentration inequalities using the entropy method
• On random minimum length spanning trees
• On the difference of expected lengths of minimum spanning trees
• On the length of a random minimum spanning tree
• On the value of a random minimum spanning tree problem
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Random minimum length spanning trees in regular graphs
• The constrained minimum spanning tree problem
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph

Cited in

(10)

• Random-tree diameter and the diameter-constrained MST
• Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
• OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS
• A randomly weighted minimum arborescence with a random cost constraint
• Random-tree Diameter and the Diameter-constrained MST
• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• The lower tail of the random minimum spanning tree
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• On finding a minimum spanning tree in a network with random weights
• Minimum-weight combinatorial structures under random cost-constraints

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

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