{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:15Z","timestamp":1787337615481,"version":"build-2736575974"},"reference-count":18,"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":[[2008,1]]},"abstract":"<jats:p>We show that every weighted connected graph G contains as a subgraph a spanning tree into which the edges of G can be embedded with average stretch $O (\\log^{2} n \\log \\log n)$. Moreover, we show that this tree can be constructed in time $O (m \\log n + n \\log^2 n)$ in general, and in time $O (m \\log n)$ if the input graph is unweighted. The main ingredient in our construction is a novel graph decomposition technique. Our new algorithm can be immediately used to improve the running time of the recent solver for symmetric diagonally dominant linear systems of Spielman and Teng from $ m 2^{(O (\\sqrt{\\log n\\log\\log n})) }$ to $m \\log^{O (1)}n$, and to $O ( n \\log^{2} n \\log \\log n)$ when the system is planar. Our result can also be used to improve several earlier approximation algorithms that use low-stretch spanning trees.<\/jats:p>","DOI":"10.1137\/050641661","type":"journal-article","created":{"date-parts":[[2008,5,23]],"date-time":"2008-05-23T18:05:05Z","timestamp":1211565905000},"page":"608-628","source":"Crossref","is-referenced-by-count":72,"title":["Lower-Stretch Spanning Trees"],"prefix":"10.1137","volume":"38","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Emek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel A.","family":"Spielman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,5,23]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      Probabilistic approximation of metric spaces and its algorithmic applications\n                      , in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 184\u2013193.","DOI":"10.1109\/SFCS.1996.548477"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      On approximating arbitrary metrices by tree metrics\n                      , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"R5","unstructured":"Y. Bartal,\n                      private communication\n                      , 2005."},{"key":"R6","unstructured":"E. Boman and B. Hendrickson,\n                      On Spanning Tree Preconditioners\n                      , manuscript, Sandia National Labs, Livermore, CA, 2001."},{"key":"R7","unstructured":"E. Boman, B. Hendrickson, and S. Vavasis,\n                      Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners\n                      , manuscript, Sandia National Labs, Livermore, CA, and Cornell University, Ithaca, NY, available online from http:\/\/arXiv.org\/ abs\/cs\/0407022 (2004)."},{"key":"R8","unstructured":"P. Crescenzi and V. Kann, eds.\n                      A Compendium of NP Optimization Problems\n                      , http:\/\/ www.nada.kth.se\/$\\!_{^{\\sim}}\\!$viggo\/problemlist\/."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Y. Emek and D. Peleg,\n                      A tight upper bound on the probabilistic embedding of series-parallel graphs\n                      , in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 1045\u20131053.","DOI":"10.1145\/1109557.1109673"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347478"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"J. Fakcharoenphol, S. Rao, and K. Talwar,\n                      A tight bound on approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 448\u2013455.","DOI":"10.1145\/780542.780608"},{"key":"R12","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to Theory of NP-Completeness\n                      , W. H. Freeman, New York, 1979."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair,\n                      Cuts, trees and \\( \\ell_l \\)-embeddings of graphs\n                      , in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 399\u2013408.","DOI":"10.1109\/SFFCS.1999.814611"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0203015"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"D. Peleg and E. Reshef,\n                      Deterministic polylogarithmic approximation for minimum communication spanning trees\n                      , in Proceedings of the 25th International Colloquium on Automata, Languages and Programming, 1998, pp. 670\u2013681.","DOI":"10.1007\/BFb0055092"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"D. A. Spielman and S.H. Teng,\n                      Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems\n                      , in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 81\u201390.","DOI":"10.1145\/1007352.1007372"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050641661","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:25Z","timestamp":1787336425000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050641661"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/050641661"],"URL":"https:\/\/doi.org\/10.1137\/050641661","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}