{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:09:36Z","timestamp":1775912976236,"version":"3.50.1"},"reference-count":33,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,4,19]],"date-time":"2018-04-19T00:00:00Z","timestamp":1524096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We consider the problem of uniformly generating a spanning tree for an undirected connected graph. This process is useful for computing statistics, namely for phylogenetic trees. We describe a Markov chain for producing these trees. For cycle graphs, we prove that this approach significantly outperforms existing algorithms. For general graphs, experimental results show that the chain converges quickly. This yields an efficient algorithm due to the use of proper fast data structures. To obtain the mixing time of the chain we describe a coupling, which we analyze for cycle graphs and simulate for other graphs.<\/jats:p>","DOI":"10.3390\/a11040053","type":"journal-article","created":{"date-parts":[[2018,4,20]],"date-time":"2018-04-20T04:24:21Z","timestamp":1524198261000},"page":"53","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Linking and Cutting Spanning Trees"],"prefix":"10.3390","volume":"11","author":[{"given":"Lu\u00eds M. S.","family":"Russo","sequence":"first","affiliation":[{"name":"INESC-ID and the Department of Computer Science and Engineering, Instituto Superior T\u00e9cnico, Universidade de Lisboa, Avenida Rovisco Pais 1, 1049-001 Lisboa, Portugal"}]},{"given":"Andreia Sofia","family":"Teixeira","sequence":"additional","affiliation":[{"name":"INESC-ID and the Department of Computer Science and Engineering, Instituto Superior T\u00e9cnico, Universidade de Lisboa, Avenida Rovisco Pais 1, 1049-001 Lisboa, Portugal"}]},{"given":"Alexandre P.","family":"Francisco","sequence":"additional","affiliation":[{"name":"INESC-ID and the Department of Computer Science and Engineering, Instituto Superior T\u00e9cnico, Universidade de Lisboa, Avenida Rovisco Pais 1, 1049-001 Lisboa, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2018,4,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Aigner, M., Ziegler, G.M., and Quarteroni, A. (2010). Proofs from the Book, Springer.","DOI":"10.1007\/978-3-642-00856-6"},{"key":"ref_2","unstructured":"Borchardt, C.W. (1860). \u00dcber Eine Interpolationsformel f\u00fcr Eine Art Symmetrischer Functionen und \u00fcber Deren Anwendung, Math. Abh. der Akademie der Wissenschaften zu Berlin."},{"key":"ref_3","first-page":"376","article-title":"A theorem on trees","volume":"23","author":"Cayley","year":"1889","journal-title":"Q. J. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1145\/364099.364331","article-title":"An improved equivalence algorithm","volume":"7","author":"Galler","year":"1964","journal-title":"Commun. ACM"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","article-title":"Self-adjusting binary search trees","volume":"32","author":"Sleator","year":"1985","journal-title":"J. ACM"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., and Upfal, E. (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Levin, D.A., and Peres, Y. (2017). Markov Chains and Mixing Times, American Mathematical Society.","DOI":"10.1090\/mbk\/107"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1017\/S0963548300000390","article-title":"Improved bounds for mixing rates of Markov chains and multicommodity flow","volume":"1","author":"Sinclair","year":"1992","journal-title":"Comb. Probab. Comput."},{"key":"ref_9","unstructured":"Bubley, R., and Dyer, M. (1997, January 20\u201322). Path coupling: A technique for proving rapid mixing in Markov chains. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, USA."},{"key":"ref_10","unstructured":"Kumar, V.S.A., and Ramesh, H. (1999, January 17\u201319). Markovian coupling vs. conductance for the Jerrum-Sinclair chain. Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York, NY, USA."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1137\/0218077","article-title":"Approximating the permanent","volume":"18","author":"Jerrum","year":"1989","journal-title":"SIAM J. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1089\/106652703322539024","article-title":"Duplication models for biological networks","volume":"10","author":"Chung","year":"2003","journal-title":"J. Comput. Biol."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Chung, F.R., and Lu, L. (2006). Complex Graphs and Networks, American Mathematical Society. No. 107.","DOI":"10.1090\/cbms\/107"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Lyons, R., and Peres, Y. (2016). Probability on Trees and Networks, Cambridge University Press.","DOI":"10.1017\/9781316672815"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1137\/0403039","article-title":"The random walk construction of uniform spanning trees and uniform labelled trees","volume":"3","author":"Aldous","year":"1990","journal-title":"SIAM J. Discret. Math."},{"key":"ref_16","unstructured":"Broader, A. (November, January 30). Generating random spanning trees. Proceedings of the IEEE Symposium on Fondations of Computer Science, Research Triangle Park, NC, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1002\/rsa.3240010402","article-title":"A random tree model associated with random graphs","volume":"1","author":"Aldous","year":"1990","journal-title":"Random Struct. Algorithms"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Wilson, D.B. (1996, January 22\u201324). Generating random spanning trees more quickly than the cover time. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC \u201996), Philadelphia, PA, USA.","DOI":"10.1145\/237814.237880"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1002\/andp.18471481202","article-title":"Ueber die aufl\u00f6sung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer str\u00f6me gef\u00fchrt wird","volume":"148","author":"Kirchhoff","year":"1847","journal-title":"Ann. Phys."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0196-6774(83)90022-6","article-title":"Random spanning tree","volume":"4","year":"1983","journal-title":"J. Algorithms"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0196-6774(90)90002-V","article-title":"Generating random combinatorial objects","volume":"11","author":"Kulkarni","year":"1990","journal-title":"J. Algorithms"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0196-6774(89)90016-3","article-title":"Unranking and ranking spanning trees of a graph","volume":"10","author":"Colbourn","year":"1989","journal-title":"J. Algorithms"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1006\/jagm.1996.0014","article-title":"Two algorithms for unranking arborescences","volume":"20","author":"Colbourn","year":"1996","journal-title":"J. Algorithms"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., and M\u0105dry, A. (2009, January 24\u201327). Faster generation of random spanning trees. Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, USA.","DOI":"10.1109\/FOCS.2009.75"},{"key":"ref_25","unstructured":"M\u0105dry, A. (2011). From Graphs to Matrices, and Back: New Techniques For Graph Algorithms. [Ph.D. Thesis, Massachusetts Institute of Technology]."},{"key":"ref_26","unstructured":"Indyk, P. (2015, January 4\u20136). Fast generation of random spanning trees and the effective resistance metric. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Feder, T., and Mihail, M. (1992, January 4\u20136). Balanced matroids. Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, Victoria, BC, Canada.","DOI":"10.1145\/129712.129716"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1741","DOI":"10.1214\/105051604000000639","article-title":"Elementary bounds on poincar\u00e9 and log-sobolev constants for decomposable markov chains","volume":"14","author":"Jerrum","year":"2004","journal-title":"Ann. Appl. Probab."},{"key":"ref_29","unstructured":"Mihail, M. (November, January 30). Conductance and convergence of markov chains-a combinatorial treatment of expanders. Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, NC, USA."},{"key":"ref_30","unstructured":"Jerrum, M., and Son, J.-B. (2002, January 19). Spectral gap and log-sobolev constant for balanced matroids. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, BC, Canada."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Sleator, D.D., and Tarjan, R.E. (1981, January 11\u201313). A data structure for dynamic trees. Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing (STOC \u201981), Milwaukee, WI, USA.","DOI":"10.1145\/800076.802464"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1145\/76359.76368","article-title":"Finding minimum-cost circulations by canceling negative cycles","volume":"36","author":"Goldberg","year":"1989","journal-title":"J. ACM"},{"key":"ref_33","unstructured":"Henzinger, M.R., and King, V. (June, January 29). Randomized dynamic graph algorithms with polylogarithmic time per operation. Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, Las Vegas, NV, USA."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/53\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:01:24Z","timestamp":1760194884000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,19]]},"references-count":33,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,4]]}},"alternative-id":["a11040053"],"URL":"https:\/\/doi.org\/10.3390\/a11040053","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,19]]}}}