{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T11:45:04Z","timestamp":1750938304777},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_39","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T08:09:41Z","timestamp":1458547781000},"page":"522-535","source":"Crossref","is-referenced-by-count":4,"title":["Generating Random Spanning Trees via Fast Matrix Multiplication"],"prefix":"10.1007","author":[{"given":"Nicholas J. A.","family":"Harvey","sequence":"first","affiliation":[]},{"given":"Keyulu","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"key":"39_CR1","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/0403039","volume":"3","author":"D Aldous","year":"1990","unstructured":"Aldous, D.: The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discrete Math. 3, 450\u2013465 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"39_CR2","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M., Madry, A., Gharan, S.O., Saberi, A.: An $${O}$$ O (log $$n$$ n \/log log $$n$$ n )-approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of SODA (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Broder, A.: Generating random spanning trees. In: Proceedings of FOCS, pp. 442\u2013447 (1989)","DOI":"10.1109\/SFCS.1989.63516"},{"key":"39_CR4","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1090\/S0025-5718-1974-0331751-8","volume":"28","author":"JR Bunch","year":"1974","unstructured":"Bunch, J.R., Hopcroft, J.E.: Triangular factorization and inversion by fast matrix multiplication. Math. Comput. 28, 231\u2013236 (1974)","journal-title":"Math. Comput."},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Campbell, S.L., Meyer, C.D.: Generalized Inverses of Linear Transformations. SIAM (1973)","DOI":"10.1137\/0125057"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondrak, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: Proceedings of FOCS (2010)","DOI":"10.1109\/FOCS.2010.60"},{"key":"39_CR7","first-page":"217","volume":"62","author":"CJ Colbourn","year":"1988","unstructured":"Colbourn, C.J., Debroni, B.M., Myrvold, W.J.: Estimating the coefficients of the reliability polynomial. Congr. Numer. 62, 217\u2013223 (1988)","journal-title":"Congr. Numer."},{"key":"39_CR8","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0196-6774(89)90016-3","volume":"10","author":"CJ Colbourn","year":"1989","unstructured":"Colbourn, C.J., Day, R.P.J., Nel, L.D.: Unranking and ranking spanning trees of a graph. J. Algor. 10, 271\u2013286 (1989)","journal-title":"J. Algor."},{"key":"39_CR9","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1006\/jagm.1996.0014","volume":"20","author":"CJ Colbourn","year":"1996","unstructured":"Colbourn, C.J., Myrvold, W.J., Neufeld, E.: Two algorithms for unranking arborescences. J. Algor. 20, 268\u2013281 (1996)","journal-title":"J. Algor."},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of FOCS (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"Goyal, N., Rademacher, L., Vempala, S.: Expanders via random spanning trees. In: Proceedings of SODA (2009)","DOI":"10.1137\/1.9781611973068.64"},{"key":"39_CR12","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/0196-6774(83)90022-6","volume":"4","author":"A Gu\u00e9noche","year":"1983","unstructured":"Gu\u00e9noche, A.: Random spanning tree. J. Algor. 4, 214\u2013220 (1983)","journal-title":"J. Algor."},{"key":"39_CR13","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1137\/070684008","volume":"39","author":"NJA Harvey","year":"2009","unstructured":"Harvey, N.J.A.: Algebraic algorithms for matching and matroid problems. SIAM J. Comput. 39, 679\u2013702 (2009)","journal-title":"SIAM J. Comput."},{"key":"39_CR14","doi-asserted-by":"crossref","unstructured":"Harvey, N.J.A., Olver, N.: Pipage rounding, pessimistic estimators and matrix concentration. In: Proceedings of SODA (2014)","DOI":"10.1137\/1.9781611973402.69"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., Madry, A.: Faster generation of random spanning trees. In: Proceedings of FOCS (2009)","DOI":"10.1109\/FOCS.2009.75"},{"key":"39_CR16","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1002\/andp.18471481202","volume":"72","author":"G Kirchhoff","year":"1847","unstructured":"Kirchhoff, G.: \u00dcber die Aufl\u00f6sung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Str\u00f6me gef\u00fchrt wird. Ann. Phys. und Chem. 72, 497\u2013508 (1847)","journal-title":"Ann. Phys. und Chem."},{"issue":"10","key":"39_CR17","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/2347736.2347759","volume":"55","author":"I Koutis","year":"2012","unstructured":"Koutis, I., Miller, G.L., Peng, R.: A fast solver for a class of linear systems. Commun. ACM 55(10), 99\u2013107 (2012)","journal-title":"Commun. ACM"},{"issue":"2","key":"39_CR18","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0196-6774(90)90002-V","volume":"11","author":"VG Kulkarni","year":"1990","unstructured":"Kulkarni, V.G.: Generating random combinatorial objects. J. Algor. 11(2), 185\u2013207 (1990)","journal-title":"J. Algor."},{"key":"39_CR19","unstructured":"Lyons, R., Peres, Y.: Probability on Trees and Networks. Cambridge University Press (in preparation). Current version available at http:\/\/pages.iu.edu\/~rdlyons\/"},{"key":"39_CR20","doi-asserted-by":"crossref","unstructured":"Madry, A., Straszak, D., Tarnawski, J.: Fast generation of random spanning trees and the effective resistance metric. In: Proceedings of SODA (2015)","DOI":"10.1137\/1.9781611973730.134"},{"key":"39_CR21","doi-asserted-by":"crossref","unstructured":"Wilson, D.B.: Generating random spanning trees more quickly than the cover time. In: Proceedings of STOC (1996)","DOI":"10.1145\/237814.237880"}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,15]],"date-time":"2024-06-15T04:47:05Z","timestamp":1718426825000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}