On the random 2-stage minimum spanning tree

DOI10.1002/rsa.20079zbMath1089.60010OpenAlexW4232237158WikidataQ57401503 ScholiaQ57401503MaRDI QIDQ3376662

Abraham D. Flaxman, Michael Krivelevich, Alan M. Frieze

Publication date: 24 March 2006

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20079

zbMATH Keywords

uncertaintystochastic programmingspanning tree problemthreshold heuristic

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Stochastic programming (90C15) Combinatorial probability (60C05) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (8)

Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty ⋮ On the approximability of robust spanning tree problems ⋮ Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms ⋮ On greedy approximation algorithms for a class of two-stage stochastic assignment problems ⋮ Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation ⋮ Two-stage combinatorial optimization problems under risk ⋮ The submodularity of two-stage stochastic maximum-weight independent set problems ⋮ Typical values of extremal-weight combinatorial structures with independent symmetric weights

Cites Work

• Introduction to Stochastic Programming

This page was built for publication: On the random 2-stage minimum spanning tree