Covering minimum spanning trees of random subgraphs

DOI10.1002/rsa.20115zbMath1108.05082OpenAlexW4256214929MaRDI QIDQ3419593

Jan Vondrák, Michel X. Goemans

Publication date: 7 February 2007

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

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

zbMATH Keywords

random modelshigh probabilityrandom subset

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (3)

Set selection under explorable stochastic uncertainty via covering techniques ⋮ A tight bound on the collection of edges in MSTs of induced subgraphs ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Covering minimum spanning trees of random subgraphs