{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:51Z","timestamp":1787340831906,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of a small number of spanning trees of a graph. We prove that for any bounded-degree $n$-vertex graph, the union of two uniformly random spanning trees approximates the expansion of the graph to within a factor of $O(\\log n)$. For the complete graph, we prove that the union of two uniformly random spanning trees is an expander with high probability. For the random graph $G_{n,p}$, for $p = \\Omega(\\log{n}\/n)$, we give a randomized algorithm for constructing two spanning trees whose union is an expander. A closely related construction, which we call a selector, has similar properties. A random selector of a graph is obtained by starting with any spanning tree of the graph and adding a small number of random edges at each vertex.<\/jats:p>","DOI":"10.1137\/120890971","type":"journal-article","created":{"date-parts":[[2014,3,25]],"date-time":"2014-03-25T11:11:26Z","timestamp":1395745886000},"page":"497-513","source":"Crossref","is-referenced-by-count":6,"title":["Expanders via Random Spanning Trees"],"prefix":"10.1137","volume":"43","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Navin","family":"Goyal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luis","family":"Rademacher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,3,25]]},"reference":[{"key":"atypb1","first-page":"20","author":"Abraham I.","year":"2004","journal-title":"ACM"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/0403039"},{"key":"atypb3","first-page":"518","author":"Alon N.","year":"2007","journal-title":"FOCS"},{"key":"atypb4","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 2nd ed., Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, New York, 2000."},{"key":"atypb5","unstructured":"J. Batson, D. A. Spielman, and N. Srivastava,\n                      Twice-Ramanujan sparsifiers\n                      , arXiv: 0808.0163v1, 2008."},{"key":"atypb6","first-page":"47","author":"Bencz\u00far A. A.","year":"1996","journal-title":"Proceedings of STOC"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s,\n                      Random Graphs\n                      , 2nd ed., Cambridge University Press, Cambridge, 2001.","DOI":"10.1017\/CBO9780511814068"},{"key":"atypb8","first-page":"442","author":"Broder A. Z.","year":"1989","journal-title":"Proceedings of FOCS"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M"},{"key":"atypb10","first-page":"26","author":"Feder T.","year":"1992","journal-title":"ACM"},{"key":"atypb11","unstructured":"O. Goldreich,\n                      Randomized Methods in Computation, Lecture\n                      2, http:\/\/www.wisdom. oded\/rnd.html}weizmann.ac.il\/\u02dcoded\/rnd.html (2001)."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"atypb14","first-page":"353","author":"Lov\u00e1sz L.","year":"1996","journal-title":"Budapest"},{"key":"atypb15","unstructured":"R. Lyons and Y. Peres,\n                      Probability on Trees and Networks\n                      , preprint http:\/\/mypage.iu. rdlyons\/prbtree\/prbtree.html}edu\/\\string rdlyons\/prbtree\/prbtree.html (2005)."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.009"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. Motiwala, M. Elmore, N. Feamster, and S. Vempala,\n                      Path splicing\n                      , in Proceedings of ACM SIGCOMM, Seattle, WA, 2008.","DOI":"10.1145\/1402958.1402963"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"M. Motiwala, N. Feamster, and S. Vempala,\n                      Path splicing: Reliable connectivity with rapid recovery\n                      , in Proceedings of the 6th ACM SIGCOMM HotNets Workshop, Atlanta, GA, 2007.","DOI":"10.1145\/1402958.1402963"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1063\/1.533200"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0917"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"atypb23","unstructured":"S. Shenker,\n                      We dream of geni: Exploring radical network designs\n                      , in Proceedings of FCRC, http:\/\/lazowska.cs.washington.edu\/fcrc\/Shenker.FCRC.pdf (2007)."},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"D. Spielman and N. Srivastava,\n                      Graph sparsification by effective resistances\n                      , in Proceedings of STOC, 2008.","DOI":"10.1145\/1374376.1374456"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120890971","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:51:07Z","timestamp":1787338267000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120890971"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/120890971"],"URL":"https:\/\/doi.org\/10.1137\/120890971","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}