{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:22:18Z","timestamp":1777965738334,"version":"3.51.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T00:00:00Z","timestamp":1362096000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,10]]},"DOI":"10.1007\/s00224-013-9444-5","type":"journal-article","created":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T04:16:03Z","timestamp":1362111363000},"page":"521-554","source":"Crossref","is-referenced-by-count":21,"title":["Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs"],"prefix":"10.1007","volume":"55","author":[{"given":"Guy E.","family":"Blelloch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioannis","family":"Koutis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gary L.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kanat","family":"Tangwongsan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,3,1]]},"reference":[{"key":"9444_CR1","first-page":"781","volume-title":"FOCS","author":"I. Abraham","year":"2008","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Nearly tight low stretch spanning trees. In: FOCS, pp. 781\u2013790 (2008)"},{"issue":"1","key":"9444_CR2","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N. Alon","year":"1995","unstructured":"Alon, N., Karp, R.M., Peleg, D., West, D.: A\u00a0graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24(1), 78\u2013100 (1995)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9444_CR3","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B. Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. J.\u00a0Assoc. Comput. Mach. 32(4), 804\u2013823 (1985)","journal-title":"J.\u00a0Assoc. Comput. Mach."},{"key":"9444_CR4","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S. Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"key":"9444_CR5","first-page":"273","volume-title":"STOC","author":"P. Christiano","year":"2011","unstructured":"Christiano, P., Kelner, J.A., Madry, A., Spielman, D.A., Teng, S.H.: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In: STOC, pp. 273\u2013282 (2011)"},{"issue":"3","key":"9444_CR6","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0012-365X(79)90084-0","volume":"25","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: The tail of the hypergeometric distribution. Discrete Math. 25(3), 285\u2013287 (1979)","journal-title":"Discrete Math."},{"key":"9444_CR7","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1109\/SFCS.1993.366822","volume-title":"Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science","author":"E. Cohen","year":"1993","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. In: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, pp. 648\u2013658. IEEE Computer Society, Washington (1993). doi: 10.1109\/SFCS.1993.366822 . http:\/\/portal.acm.org\/citation.cfm?id=1398517.1398961"},{"issue":"1","key":"9444_CR8","first-page":"132","volume":"47","author":"E. Cohen","year":"2000","unstructured":"Cohen, E.: Polylog-time and near-linear work approximation scheme for undirected shortest paths. J.\u00a0ACM 47(1), 132\u2013166 (2000)","journal-title":"J.\u00a0ACM"},{"key":"9444_CR9","unstructured":"Daitch, S.I., Spielman, D.A.: Faster approximate lossy generalized flow via interior point algorithms. CoRR (2008). arXiv:0803.0988"},{"key":"9444_CR10","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1145\/1060590.1060665","volume-title":"Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing","author":"M. Elkin","year":"2005","unstructured":"Elkin, M., Emek, Y., Spielman, D.A., Teng, S.H.: Lower-stretch spanning trees. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 494\u2013503. ACM Press, New York (2005). doi: 10.1145\/1060590.1060665"},{"key":"9444_CR11","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1996","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)","edition":"3"},{"key":"9444_CR12","unstructured":"Gremban, K.: Combinatorial preconditioners for sparse, symmetric, diagonally dominant linear systems. Ph.D. thesis, Carnegie Mellon University, Pittsburgh (1996). CMU CS Tech Report CMU-CS-96-123"},{"issue":"301","key":"9444_CR13","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963). doi: 10.2307\/2282952","journal-title":"J. Am. Stat. Assoc."},{"key":"9444_CR14","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1992","unstructured":"J\u00e1J\u00e1, J.: An Introduction to Parallel Algorithms. Addison-Wesley, Reading (1992)"},{"key":"9444_CR15","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"440","volume-title":"28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)","author":"J.A. Kelner","year":"2011","unstructured":"Kelner, J.A., Levin, A.: Spectral sparsification in the semi-streaming setting. In: Schwentick,\u00a0T., D\u00fcrr,\u00a0C. (eds.) 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), vol. 9, pp. 440\u2013451. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl (2011)"},{"issue":"2","key":"9444_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.1997.0888","volume":"25","author":"P.N. Klein","year":"1997","unstructured":"Klein, P.N., Subramanian, S.: A randomized parallel algorithm for single-source shortest paths. J.\u00a0Algorithms 25(2), 205\u2013220 (1997)","journal-title":"J.\u00a0Algorithms"},{"key":"9444_CR17","unstructured":"Koutis, I.: Combinatorial and algebraic algorithms for optimal multilevel algorithms. Ph.D. thesis, Carnegie Mellon University, Pittsburgh (2007). CMU CS Tech Report CMU-CS-07-131"},{"key":"9444_CR18","first-page":"1002","volume-title":"SODA","author":"I. Koutis","year":"2007","unstructured":"Koutis, I., Miller, G.L.: A\u00a0linear work, O(n 1\/6) time, parallel algorithm for solving planar Laplacians. In: SODA, pp. 1002\u20131011 (2007)"},{"key":"9444_CR19","first-page":"235","volume-title":"FOCS","author":"I. Koutis","year":"2010","unstructured":"Koutis, I., Miller, G.L., Peng, R.: Approaching optimality for solving SDD linear systems. In: FOCS, pp. 235\u2013244 (2010)"},{"key":"9444_CR20","first-page":"590","volume-title":"FOCS","author":"I. Koutis","year":"2011","unstructured":"Koutis, I., Miller, G.L., Peng, R.: A nearly mlogn time solver for SDD linear systems. In: FOCS, pp. 590\u2013598 (2011). doi: 10.1109\/FOCS.2011.85"},{"key":"9444_CR21","volume-title":"Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes","author":"F.T. Leighton","year":"1992","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes. Morgan Kaufmann Publishers, San Francisco (1992)"},{"key":"9444_CR22","first-page":"47","volume-title":"Randomness and Computation","author":"G.L. Miller","year":"1989","unstructured":"Miller, G.L., Reif, J.H.: Parallel tree contraction part 1: fundamentals. In: Micali, S. (ed.) Randomness and Computation, vol. 5, pp. 47\u201372. JAI Press, Greenwich (1989)"},{"issue":"6","key":"9444_CR23","doi-asserted-by":"crossref","first-page":"1227","DOI":"10.1137\/0222073","volume":"22","author":"V.Y. Pan","year":"1993","unstructured":"Pan, V.Y., Reif, J.H.: Fast and efficient parallel solution of sparse linear systems. SIAM J. Comput. 22(6), 1227\u20131250 (1993)","journal-title":"SIAM J. Comput."},{"key":"9444_CR24","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718812","volume-title":"A Mathematical View of Interior-Point Methods in Convex Optimization","author":"J. Renegar","year":"2001","unstructured":"Renegar, J.: A Mathematical View of Interior-Point Methods in Convex Optimization. Society for Industrial and Applied Mathematics, Philadelphia (2001)"},{"issue":"6","key":"9444_CR25","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"Schieber, B., Vishkin, U.: On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput. 17(6), 1253\u20131262 (1988). doi: 10.1137\/0217079","journal-title":"SIAM J. Comput."},{"key":"9444_CR26","unstructured":"Skala, M.: Hypergeometric tail inequalities: ending the insanity (2009). http:\/\/ansuz.sooke.bc.ca\/professional\/hypergeometric.pdf"},{"key":"9444_CR27","volume-title":"Proceedings of the International Congress of Mathematicians","author":"D.A. Spielman","year":"2010","unstructured":"Spielman, D.A.: Algorithms, graph theory, and linear equations in Laplacian matrices. In: Proceedings of the International Congress of Mathematicians (2010)"},{"key":"9444_CR28","first-page":"563","volume-title":"STOC","author":"D.A. Spielman","year":"2008","unstructured":"Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. In: STOC, pp. 563\u2013568 (2008)"},{"key":"9444_CR29","unstructured":"Spielman, D.A., Teng, S.H.: Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR (2006). arXiv:cs\/0607105"},{"key":"9444_CR30","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/978-3-642-13562-0_2","volume-title":"Theory and Applications of Models of Computation","author":"S.H. Teng","year":"2010","unstructured":"Teng, S.H.: The Laplacian paradigm: emerging algorithms for massive graphs. In: Theory and Applications of Models of Computation, pp. 2\u201314 (2010)"},{"issue":"1","key":"9444_CR31","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1137\/0220006","volume":"20","author":"J.D. Ullman","year":"1991","unstructured":"Ullman, J.D., Yannakakis, M.: High-probability parallel transitive-closure algorithms. SIAM J. Comput. 20(1), 100\u2013125 (1991). doi: 10.1137\/0220006","journal-title":"SIAM J. Comput."},{"key":"9444_CR32","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032701","volume-title":"Interior Point Algorithms: Theory and Analysis","author":"Y. Ye","year":"1997","unstructured":"Ye, Y.: Interior Point Algorithms: Theory and Analysis. Wiley, New York (1997). http:\/\/www.worldcat.org\/oclc\/36746523"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9444-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9444-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9444-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T18:46:19Z","timestamp":1644432379000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9444-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,1]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["9444"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9444-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,1]]}}}