{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T01:28:24Z","timestamp":1776216504212,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":23,"publisher":"ACM","license":[{"start":{"date-parts":[[2004,6,13]],"date-time":"2004-06-13T00:00:00Z","timestamp":1087084800000},"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":[[2004,6,13]]},"DOI":"10.1145\/1007352.1007372","type":"proceedings-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T15:55:38Z","timestamp":1090338938000},"page":"81-90","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":406,"title":["Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems"],"prefix":"10.1145","author":[{"given":"Daniel A.","family":"Spielman","sequence":"first","affiliation":[{"name":"M.I.T., Cambridge, MA"}]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA and Akamai Technologies Inc."}]}],"member":"320","published-online":{"date-parts":[[2004,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380858"},{"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\/237814.237827"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384019"},{"key":"e_1_3_2_1_5_1","unstructured":"E. Boman D. Chen B. Hendrickson and S. Toledo. Maximum-weight-basis preconditioners. to appear in Numerical Linear Algebra and Applications.  E. Boman D. Chen B. Hendrickson and S. Toledo. Maximum-weight-basis preconditioners. to appear in Numerical Linear Algebra and Applications."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801390637"},{"key":"e_1_3_2_1_7_1","volume-title":"Sandia National Lab.","author":"Boman E.","year":"2001","unstructured":"E. Boman and B. Hendrickson . On spanning tree preconditioners. Manuscript , Sandia National Lab. , 2001 . E. Boman and B. Hendrickson. On spanning tree preconditioners. Manuscript, Sandia National Lab., 2001."},{"issue":"3","key":"e_1_3_2_1_8_1","first-page":"938","article-title":"Algorithms for partitioning graphs and computer logic based on eigenvectors of connection matrices","volume":"15","author":"Donath W. E.","year":"1972","unstructured":"W. E. Donath and A. J. Hoffman . Algorithms for partitioning graphs and computer logic based on eigenvectors of connection matrices . IBM Technical Disclosure Bulletin , 15 ( 3 ): 938 -- 944 , 1972 . W. E. Donath and A. J. Hoffman. Algorithms for partitioning graphs and computer logic based on eigenvectors of connection matrices. IBM Technical Disclosure Bulletin, 15(3):938--944, 1972.","journal-title":"IBM Technical Disclosure Bulletin"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.175.0420"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796408"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579329"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01397553"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/645605.663051"},{"key":"e_1_3_2_1_16_1","volume-title":"UIUC","author":"Joshi A.","year":"1997","unstructured":"A. Joshi . Topics in Optimization and Sparse Linear Systems. PhD thesis , UIUC , 1997 . A. Joshi. Topics in Optimization and Sparse Linear Systems. PhD thesis, UIUC, 1997."},{"key":"e_1_3_2_1_17_1","volume-title":"Version 4.","author":"Karypis G.","year":"1998","unstructured":"G. Karypis and V. Kumar . MeTis: Unstructured Graph Partitioning and Sparse Matrix Ordering System , Version 4. 0, Sept. 1998 . G. Karypis and V. Kumar. MeTis: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 4. 0, Sept. 1998."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040402"},{"key":"e_1_3_2_1_21_1","volume-title":"Solving symmetric diagonally-dominant systems by preconditioning","author":"Maggs B. M.","year":"2002","unstructured":"B. M. Maggs , G. L. Miller , O. Parekh , R. Ravi , and S. L. M. Woo . Solving symmetric diagonally-dominant systems by preconditioning . 2002 . B. M. Maggs, G. L. Miller, O. Parekh, R. Ravi, and S. L. M. Woo. Solving symmetric diagonally-dominant systems by preconditioning. 2002."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(98)00191-6"},{"key":"e_1_3_2_1_23_1","first-page":"416","volume-title":"44th Annual IEEE FOCS","author":"Spielman D.","year":"2003","unstructured":"D. Spielman and S. -H. Teng . Solving sparse, symmetric, diagonally-dominant linear systems in time O(m1. 31) . In 44th Annual IEEE FOCS , pages 416 -- 427 , 2003 . Most recent version available at http:\/\/arxiv. org\/cs. DS\/0310036. D. Spielman and S. -H. Teng. Solving sparse, symmetric, diagonally-dominant linear systems in time O(m1. 31). In 44th Annual IEEE FOCS, pages 416--427, 2003. Most recent version available at http:\/\/arxiv. org\/cs. DS\/0310036."},{"key":"e_1_3_2_1_24_1","volume-title":"Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.","author":"Spielman D. A.","year":"2003","unstructured":"D. A. Spielman and S. -H. Teng . Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. available at http:\/\/arxiv. org\/abs\/cs. DS\/0310051, 2003 . D. A. Spielman and S. -H. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. available at http:\/\/arxiv. org\/abs\/cs. DS\/0310051, 2003."},{"key":"e_1_3_2_1_25_1","volume-title":"Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript UIUC","author":"Vaidya P. M.","year":"1990","unstructured":"P. M. Vaidya . Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript UIUC 1990 . A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991, Minneapolis ., 1990. P. M. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript UIUC 1990. A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991, Minneapolis., 1990."}],"event":{"name":"STOC04: Symposium of Theory of Computing 2004","location":"Chicago IL USA","acronym":"STOC04","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-sixth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1007352.1007372","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1007352.1007372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:23:55Z","timestamp":1750267435000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1007352.1007372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6,13]]},"references-count":23,"alternative-id":["10.1145\/1007352.1007372","10.1145\/1007352"],"URL":"https:\/\/doi.org\/10.1145\/1007352.1007372","relation":{},"subject":[],"published":{"date-parts":[[2004,6,13]]},"assertion":[{"value":"2004-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}