{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:21:47Z","timestamp":1777965707269,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316381","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"377-388","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Dynamic low-stretch trees via dynamic low-diameter decompositions"],"prefix":"10.1145","author":[{"given":"Sebastian","family":"Forster","sequence":"first","affiliation":[{"name":"University of Salzburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gramoz","family":"Goranci","sequence":"additional","affiliation":[{"name":"University of Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.62"},{"key":"e_1_3_2_1_2_1","volume-title":"International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 1\u201316","author":"Abraham Ittai","year":"2014"},{"key":"e_1_3_2_1_3_1","volume-title":"On Fully Dynamic Graph Sparsifiers. In Symposium on Foundations of Computer Science (FOCS). 335\u2013344","author":"Abraham Ittai","year":"2016"},{"key":"e_1_3_2_1_4_1","unstructured":"Ittai Abraham and Ofer Neiman. 2012.  Ittai Abraham and Ofer Neiman. 2012."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214015"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_3_2_1_7_1","unstructured":"Reid Andersen and Uriel Feige. {n. d.}. Interchanging distance and capacity in probabilistic mappings. CoRR abs\/0907.3631 ({n. d.}).  Reid Andersen and Uriel Feige. {n. d.}. Interchanging distance and capacity in probabilistic mappings. CoRR abs\/0907.3631 ({n. d.})."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00133"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344425"},{"key":"e_1_3_2_1_11_1","unstructured":"Andr\u00e1s A. Bencz\u00far and David R. Karger. 2015.  Andr\u00e1s A. Bencz\u00far and David R. Karger. 2015."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs. SIAM J. Comput. 44 2 (2015) 290\u2013319.  Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs. SIAM J. Comput. 44 2 (2015) 290\u2013319.","DOI":"10.1137\/070705970"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1018084"},{"key":"e_1_3_2_1_14_1","unstructured":"Aaron Bernstein Sebastian Forster and Monika Henzinger. 2019.  Aaron Bernstein Sebastian Forster and Monika Henzinger. 2019."},{"key":"e_1_3_2_1_15_1","volume-title":"Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. In Symposium on Discrete Algorithms (SODA). 1899\u20131918","author":"A"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9444-5"},{"key":"e_1_3_2_1_17_1","unstructured":"Greg Bodwin and Sebastian Krinninger. 2016.  Greg Bodwin and Sebastian Krinninger. 2016."},{"key":"e_1_3_2_1_18_1","volume-title":"Dynamic Spanners with Worst-Case Update Time. In European Symposium on Algorithms (ESA). 17:1\u2013 17:18","author":"Fully"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801390637"},{"key":"e_1_3_2_1_20_1","volume-title":"Near-Optimal Approximate Decremental All Pairs Shortest Paths. In Symposium on Foundations of Computer Science (FOCS). 170\u2013181","author":"Chechik Shiri","year":"2018"},{"key":"e_1_3_2_1_21_1","unstructured":"Michael B. Cohen Rasmus Kyng Gary L. Miller Jakub W. Pachocki Richard Peng Anup B. Rao and Shen Chen Xu. 2014.  Michael B. Cohen Rasmus Kyng Gary L. Miller Jakub W. Pachocki Richard Peng Anup B. Rao and Shen Chen Xu. 2014."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591833"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Michael Elkin. 2011.  Michael Elkin. 2011.","DOI":"10.12968\/sece.2011.12.139"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921666"},{"key":"e_1_3_2_1_25_1","unstructured":"Michael Elkin Yuval Emek Daniel A. Spielman and Shang-Hua Teng. 2008.  Michael Elkin Yuval Emek Daniel A. Spielman and Shang-Hua Teng. 2008."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/050641661"},{"key":"e_1_3_2_1_27_1","volume-title":"Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. In Symposium on Discrete Algorithms (SODA). 652\u2013669","author":"Elkin Michael","year":"2017"},{"key":"e_1_3_2_1_28_1","unstructured":"Yuval Emek. 2011.  Yuval Emek. 2011."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"k-Outerplanar Graphs Planar Duality and Low Stretch Spanning Trees. Algorithmica 61 1 (2011) 141\u2013160.   k-Outerplanar Graphs Planar Duality and Low Stretch Spanning Trees. Algorithmica 61 1 (2011) 141\u2013160.","DOI":"10.1007\/s00453-010-9423-z"},{"key":"e_1_3_2_1_30_1","unstructured":"David Eppstein Zvi Galil Giuseppe F. Italiano and Amnon Nissenzweig. 1997.  David Eppstein Zvi Galil Giuseppe F. Italiano and Amnon Nissenzweig. 1997."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767440"},{"key":"e_1_3_2_1_35_1","volume-title":"International Symposium on Distributed Computing (DISC). 33:1\u201333:14","author":"Haeupler Bernhard","year":"2018"},{"key":"e_1_3_2_1_36_1","volume-title":"Fully Dynamic Biconnectivity and Transitive Closure. In Symposium on Foundations of Computer Science (FOCS). 664\u2013672","author":"Henzinger Monika","year":"1995"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/140957299"},{"key":"e_1_3_2_1_38_1","unstructured":"Announced at FOCS\u201913.  Announced at FOCS\u201913."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327209"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203015"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_1_43_1","volume-title":"Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. In Symposium on Foundations of Computer Science (FOCS). 81\u201391","author":"King Valerie","year":"1999"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743021"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/110845914"},{"key":"e_1_3_2_1_47_1","volume-title":"Parallel Graph Decompositions Using Random Shifts. In Symposium on Parallelism in Algorithms and Architectures (SPAA). 196\u2013203","author":"Miller Gary L.","year":"2013"},{"key":"e_1_3_2_1_48_1","volume-title":"Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size. In Symposium on Foundations of Computer Science (FOCS). 3\u201312","author":"Moitra Ankur","year":"2009"},{"key":"e_1_3_2_1_49_1","unstructured":"Danupon Nanongkai and Thatchaphol Saranurak. 2017.  Danupon Nanongkai and Thatchaphol Saranurak. 2017."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055447"},{"key":"e_1_3_2_1_51_1","unstructured":"Danupon Nanongkai Thatchaphol Saranurak and Christian Wulff-Nilsen. 2017.  Danupon Nanongkai Thatchaphol Saranurak and Christian Wulff-Nilsen. 2017."},{"key":"e_1_3_2_1_52_1","volume-title":"Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. In Symposium on Foundations of Computer Science (FOCS). 950\u2013961","author":"Dynamic"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"crossref","unstructured":"David Peleg and Eilon Reshef. 1998. Deterministic Polylog Approximation for Minimum Communication Spanning Trees. In International Colloquium on Automata Languages and Programming. 670\u2013681.   David Peleg and Eilon Reshef. 1998. Deterministic Polylog Approximation for Minimum Communication Spanning Trees. In International Colloquium on Automata Languages and Programming. 670\u2013681.","DOI":"10.1007\/BFb0055092"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374415"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.162"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_3_2_1_57_1","unstructured":"Daniel A. Spielman and Jaeoh Woo. 2009. A Note on Preconditioning by Low-Stretch Spanning Trees. CoRR abs\/0903.2816 (2009). arXiv: 0903.2816  Daniel A. Spielman and Jaeoh Woo. 2009. A Note on Preconditioning by Low-Stretch Spanning Trees. CoRR abs\/0903.2816 (2009). arXiv: 0903.2816"},{"key":"e_1_3_2_1_58_1","unstructured":"P. M. Vaidya. {n. d.}. Solving Linear Equations with Symmetric Diagonally Dominant Matrices by Constructing Good Preconditioners. ({n. d.}). manuscript.  P. M. Vaidya. {n. d.}. Solving Linear Equations with Symmetric Diagonally Dominant Matrices by Constructing Good Preconditioners. ({n. d.}). manuscript."},{"key":"e_1_3_2_1_59_1","unstructured":"Christian Wulff-Nilsen. 2017.  Christian Wulff-Nilsen. 2017."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316381","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316381","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":60,"alternative-id":["10.1145\/3313276.3316381","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316381","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}