Covering minimum spanning trees of random subgraphs Export

@article{citeulike:828013, abstract = {We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p.Let n denote the number of vertices, choose p ? (0, 1) possibly depending on n, and let b = 1/(1 - p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n logbn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n logbn) on the size of a covering set in a matroid of rank n, which contains the minimum-weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability.}, address = {Department of Mathematics, MIT, Cambridge, Massachusetts 02139}, author = {Goemans, Michel X. and Vondr\'{a}k, Jan}, citeulike-article-id = {828013}, citeulike-linkout-0 = {http://dx.doi.org/10.1002/rsa.20115}, citeulike-linkout-1 = {http://www3.interscience.wiley.com/cgi-bin/abstract/112222777/ABSTRACT}, citeulike-linkout-2 = {http://www-math.mit.edu/~goemans/mst_rsa_final.pdf}, doi = {10.1002/rsa.20115}, journal = {Random Structures and Algorithms}, keywords = {matroids, open\_problems, probabilistic}, number = {3}, pages = {257--276}, posted-at = {2006-09-04 20:01:37}, priority = {4}, title = {Covering minimum spanning trees of random subgraphs}, url = {http://dx.doi.org/10.1002/rsa.20115}, volume = {29}, year = {2006} }

TY - JOUR ID - citeulike:828013 L3 - citeulike-article-id:828013 N2 - We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p.Let n denote the number of vertices, choose p ? (0, 1) possibly depending on n, and let b = 1/(1 - p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n logbn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n logbn) on the size of a covering set in a matroid of rank n, which contains the minimum-weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. IS - 3 JF - Random Structures and Algorithms AD - Department of Mathematics, MIT, Cambridge, Massachusetts 02139 EP - 276 TI - Covering minimum spanning trees of random subgraphs VL - 29 SP - 257 KW - matroids KW - open_problems KW - probabilistic AU - Goemans, Michel AU - Vondrák, Jan PY - 2006/// UR - http://dx.doi.org/10.1002/rsa.20115 ER -