A note on random 2-SAT with prescribed literal degrees
Colin Cooper, Alan Frieze, et al.
SODA 2002
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.
Colin Cooper, Alan Frieze, et al.
SODA 2002
Alexander D. Scott, Gregory B. Sorkin
Combinatorics Probability and Computing
Alexander D. Scott, Gregory B. Sorkin
Discrete Optimization
Maria-Florina Balcan, Nikhil Bansal, et al.
Machine Learning