A randomly weighted minimum spanning tree with a random cost constraint

DOI10.37236/9445zbMATH Open1456.05146arXiv1905.01229OpenAlexW3130835883MaRDI QIDQ2223477FDOQ2223477

Authors: Tomasz Tkocz, Alan Frieze 

Publication date: 29 January 2021

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

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.

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

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

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

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)

Cites Work

• Title not available (Why is that?)
• The constrained minimum spanning tree problem
• Concentration inequalities using the entropy method
• 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
• On the value of a random minimum spanning tree problem
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• On random minimum length spanning trees
• Title not available (Why is that?)
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• On the difference of expected lengths of minimum spanning trees
• A note on random minimum length spanning trees
• On the length of a random minimum spanning tree
• A note on log-concave random graphs

Cited In (10)

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

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)