Don Coppersmith, Gregory B. Sorkin
Random Structures and Algorithms
Let G = (V, E) be a complete n-vertex graph with distinct positive edge weights. We prove that for k ∈ {1, 2, ..., n - 1}, the set consisting of the edges of all minimum spanning trees (MSTs) over induced subgraphs of G with n - k + 1 vertices has at most n k - ((k + 1; 2)) elements. This proves a conjecture of Goemans and Vondrák [M.X. Goemans, J. Vondrák, Covering minimum spanning trees of random subgraphs, Random Structures Algorithms 29 (3) (2005) 257-276]. We also show that the result is a generalization of Mader's Theorem, which bounds the number of edges in any edge-minimal k-connected graph. © 2008 Elsevier Inc. All rights reserved.
Don Coppersmith, Gregory B. Sorkin
Random Structures and Algorithms
Robert Hildebrand, Robert Weismantel, et al.
SODA 2017
Gerald J. Tesauro, Jeffrey O. Kephart, et al.
IEEE Expert-Intelligent Systems and their Applications
Colin Cooper, Alan Frieze, et al.
Algorithmica (New York)