{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:08Z","timestamp":1787341388255,"version":"build-2736575974"},"reference-count":27,"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":[[2019,1]]},"abstract":"<jats:p>We prove that any weighted graph $G=(V,E,w)$ with $n$ points and $m$ edges has a spanning tree $T$ such that $\\sum_{\\{u,v\\}\\in E}\\frac{d_T(u,v)}{w(u,v)}=O(m\\log n\\log\\log n)$. Moreover, such a tree can be found in time $O(m\\log n\\log\\log n)$. Our result is obtained using our new petal-decomposition approach which guarantees that the radius of each cluster in the tree is at most four times the radius of the induced subgraph of the cluster in the original graph.<\/jats:p>","DOI":"10.1137\/17m1115575","type":"journal-article","created":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T12:03:00Z","timestamp":1553169780000},"page":"227-248","source":"Crossref","is-referenced-by-count":13,"title":["Using Petal-Decompositions to Build a Low Stretch Spanning Tree"],"prefix":"10.1137","volume":"48","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,3,21]]},"reference":[{"key":"atypb1","first-page":"271","author":"Abraham I.","year":"2006","journal-title":"New York"},{"key":"atypb2","first-page":"502","author":"Abraham I.","year":"2007","journal-title":"Philadelphia"},{"key":"atypb3","first-page":"781","author":"Abraham I.","year":"2008","journal-title":"Washington, DC"},{"key":"atypb4","first-page":"1650","author":"Abraham I.","year":"2018","journal-title":"Philadelphia"},{"key":"atypb5","unstructured":"R. Andersen and U. Feige,\n                      Interchanging Distance and Capacity in Probabilistic Mappings\n                      ,https:\/\/arxiv.org\/abs\/0907.3631, 2009."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"atypb7","first-page":"184","author":"Bartal Y.","year":"1996","journal-title":"Washington, DC"},{"key":"atypb8","first-page":"161","author":"Bartal Y.","year":"1998","journal-title":"New York"},{"key":"atypb9","first-page":"89","author":"Bartal Y.","year":"2004","journal-title":"Berlin"},{"key":"atypb10","first-page":"512","author":"B\u01cedoiu M.","year":"2007","journal-title":"Philadelphia"},{"key":"atypb11","first-page":"114","author":"Charikar M.","year":"1998","journal-title":"New York"},{"key":"atypb12","first-page":"95","author":"Chepoi V.","year":"2010","journal-title":"Berlin"},{"key":"atypb13","first-page":"343","author":"Cohen M. B.","year":"2014","journal-title":"New York"},{"key":"atypb14","first-page":"494","author":"Elkin M.","year":"2005","journal-title":"New York"},{"key":"atypb15","first-page":"242","author":"Elkin M.","year":"2015","journal-title":"Germany"},{"key":"atypb16","first-page":"261","author":"Emek Y.","year":"2004","journal-title":"Philadelphia"},{"key":"atypb17","first-page":"1045","author":"Emek Y.","year":"2006","journal-title":"New York"},{"key":"atypb18","first-page":"448","author":"Fakcharoenphol J.","year":"2003","journal-title":"New York"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/0203015"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897640"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"I. Koutis, G. L. Miller, and R. Peng,\n                      A nearly-m log n time solver for sdd linear systems\n                      , in Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS '11, IEEE Computer Soc., Los Alamitos, CA, 2011, pp. 590-598.","DOI":"10.1109\/FOCS.2011.85"},{"key":"atypb22","first-page":"911","author":"Kelner J. A.","year":"2013","journal-title":"New York"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"R. Kyng and S. Sachdeva,\n                      Approximate Gaussian elimination for Laplacians-fast, sparse, and simple\n                      , in Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science-FOCS 2016, IEEE Computer Soc., Los Alamitos, CA, 2016, pp. 573-582.","DOI":"10.1109\/FOCS.2016.68"},{"key":"atypb24","unstructured":"R. L. McKnight,\n                      Low-Stretch Trees for Network Visualization\n                      , Ph.D. thesis, University of British Columbia, Vancouver, BC, 2015."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.03.001"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"atypb27","first-page":"81","author":"Spielman D. A.","year":"2004","journal-title":"New York"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1115575","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:16:23Z","timestamp":1787339783000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1115575"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1115575"],"URL":"https:\/\/doi.org\/10.1137\/17m1115575","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}