{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:28Z","timestamp":1781078008194,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,4]],"date-time":"2011-06-04T00:00:00Z","timestamp":1307145600000},"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":[[2011,6,4]]},"DOI":"10.1145\/1989493.1989496","type":"proceedings-article","created":{"date-parts":[[2011,6,8]],"date-time":"2011-06-08T14:36:21Z","timestamp":1307543781000},"page":"13-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs"],"prefix":"10.1145","author":[{"given":"Guy E.","family":"Blelloch","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ioannis","family":"Koutis","sequence":"additional","affiliation":[{"name":"University of Puerto Rico, Rio Piedras, PR, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gary L.","family":"Miller","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kanat","family":"Tangwongsan","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,6,4]]},"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","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90084-0"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366822"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"e_1_3_2_1_8_1","volume-title":"Faster approximate lossy generalized flow via interior point algorithms. CoRR, abs\/0803.0988","author":"Daitch Samuel I.","year":"2008","unstructured":"Samuel I. Daitch and Daniel A. Spielman . Faster approximate lossy generalized flow via interior point algorithms. CoRR, abs\/0803.0988 , 2008 . Samuel I. Daitch and Daniel A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. CoRR, abs\/0803.0988, 2008."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060665"},{"key":"e_1_3_2_1_11_1","volume-title":"Matrix Computations","author":"Golub G. H.","year":"1996","unstructured":"G. H. Golub and C. F. Van Loan . Matrix Computations . Johns Hopkins Press , 3 rd edition, 1996 . G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins Press, 3rd edition, 1996.","edition":"3"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_1_13_1","volume-title":"An Introduction to Parallel Algorithms","author":"J\u00e1J\u00e1 Joseph","year":"1992","unstructured":"Joseph J\u00e1J\u00e1 . An Introduction to Parallel Algorithms . Addison-Wesley , 1992 . Joseph J\u00e1J\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley, 1992."},{"key":"e_1_3_2_1_14_1","first-page":"1002","volume-title":"SODA","author":"Koutis Ioannis","year":"2007","unstructured":"Ioannis Koutis and Gary L. Miller . A linear work, O(n1\/6) time, parallel algorithm for solving planar laplacians . In SODA , pages 1002 -- 1011 , 2007 . Ioannis Koutis and Gary L. Miller. A linear work, O(n1\/6) time, parallel algorithm for solving planar laplacians. In SODA, pages 1002--1011, 2007."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0888"},{"key":"e_1_3_2_1_18_1","volume-title":"Trees, Hypercubes","author":"Leighton F. Thomson","year":"1992","unstructured":"F. Thomson Leighton . Introduction to Parallel Algorithms and Architectures: Array , Trees, Hypercubes . Morgan Kaufmann Publishers Inc ., San Francisco, CA, USA, 1992 . F. Thomson Leighton. Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992."},{"key":"e_1_3_2_1_19_1","first-page":"47","volume-title":"Randomness and Computation","author":"Miller Gary L.","year":"1989","unstructured":"Gary L. Miller and John H. Reif . Parallel tree contraction part 1: Fundamentals . In Silvio Micali, editor, Randomness and Computation , pages 47 -- 72 . JAI Press , Greenwich, Connecticut , 1989 . Vol. 5 . Gary L. Miller and John H. Reif. Parallel tree contraction part 1: Fundamentals. In Silvio Micali, editor, Randomness and Computation, pages 47--72. JAI Press, Greenwich, Connecticut, 1989. Vol. 5."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/502968"},{"key":"e_1_3_2_1_21_1","volume-title":"Hypergeometric tail inequalities: ending the insanity","author":"Skala Matthew","year":"2009","unstructured":"Matthew Skala . Hypergeometric tail inequalities: ending the insanity , 2009 . Matthew Skala. Hypergeometric tail inequalities: ending the insanity, 2009."},{"key":"e_1_3_2_1_22_1","volume-title":"Linear Equations in Laplacian Matrices. In Proceedings of the International Congress of Mathematicians","author":"Spielman Daniel A.","year":"2010","unstructured":"Daniel A. Spielman . Algorithms, Graph Theory , and Linear Equations in Laplacian Matrices. In Proceedings of the International Congress of Mathematicians , 2010 . Daniel A. Spielman. Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices. In Proceedings of the International Congress of Mathematicians, 2010."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_3_2_1_24_1","first-page":"416","volume-title":"FOCS","author":"Daniel","year":"2003","unstructured":"Daniel A. Spielman and Shang-Hua Teng. Solving sparse, symmetric, diagonally-dominant linear systems in time O(m1.31) . In FOCS , pages 416 -- 427 , 2003 . Daniel A. Spielman and Shang-Hua Teng. Solving sparse, symmetric, diagonally-dominant linear systems in time O(m1.31). In FOCS, pages 416--427, 2003."},{"key":"e_1_3_2_1_25_1","volume-title":"Spielman and Shang-Hua Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105","author":"Daniel","year":"2006","unstructured":"Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105 , 2006 . Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105, 2006."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13562-0_2"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/265937"}],"event":{"name":"SPAA '11: 23rd ACM Symposium on Parallelism in Algorithms and Architectures","location":"San Jose California USA","acronym":"SPAA '11","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989493.1989496","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1989493.1989496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:56Z","timestamp":1750244396000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989493.1989496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,4]]},"references-count":25,"alternative-id":["10.1145\/1989493.1989496","10.1145\/1989493"],"URL":"https:\/\/doi.org\/10.1145\/1989493.1989496","relation":{},"subject":[],"published":{"date-parts":[[2011,6,4]]},"assertion":[{"value":"2011-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}