{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:06:39Z","timestamp":1775282799472,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":57,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642135613","type":"print"},{"value":"9783642135620","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13562-0_2","type":"book-chapter","created":{"date-parts":[[2010,5,31]],"date-time":"2010-05-31T09:08:30Z","timestamp":1275296910000},"page":"2-14","source":"Crossref","is-referenced-by-count":26,"title":["The Laplacian Paradigm: Emerging Algorithms for Massive Graphs"],"prefix":"10.1007","author":[{"given":"Shang-Hua","family":"Teng","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Nearly Tight Low Stretch Spanning Trees. In: FOCS 2008, pp. 781\u2013790 (2008)","DOI":"10.1109\/FOCS.2008.62"},{"issue":"1","key":"2_CR2","doi-asserted-by":"publisher","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 graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing\u00a024(1), 78\u2013100 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1145\/217474.217529","volume-title":"DAC 1995: Proceedings of the 32nd ACM\/IEEE conference on Design automation","author":"C.J. Alpert","year":"1995","unstructured":"Alpert, C.J., Yao, S.-Z.: Spectral partitioning: the more eigenvectors, the better. In: DAC 1995: Proceedings of the 32nd ACM\/IEEE conference on Design automation, pp. 195\u2013200. ACM, New York (1995)"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Andersen, R., Borgs, C., Chayes, J.T., Hopcroft, J.E., Jain, K., Mirrokni, V.S., Teng, S.-H.: Robust PageRank and locally computable spam detection features. In: Fourth International Workshop on Adversarial Information Retrieval on the Web. ACM International Conference Proceeding Series, pp. 69\u201376 (2008)","DOI":"10.1145\/1451983.1452000"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-77004-6_12","volume-title":"Algorithms and Models for the Web-Graph","author":"R. Andersen","year":"2007","unstructured":"Andersen, R., Borgs, C., Chayes, J.T., Hopcraft, J.E., Mirrokni, V.S., Teng, S.-H.: Local computation of pagerank contributions. In: Bonato, A., Chung, F.R.K. (eds.) WAW 2007. LNCS, vol.\u00a04863, pp. 150\u2013165. Springer, Heidelberg (2007)"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Andersen, R., Chung, F., Lang, K.: Local graph partitioning using pagerank vectors. In: Proceedings: 47th Annual Symposium on Foundations of Computer Science, pp. 475\u2013486 (2006)","DOI":"10.1109\/FOCS.2006.44"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Andersen, R., Peres, Y.: Finding sparse cuts locally using evolving sets. In: STOC, pp. 235\u2013244 (2009)","DOI":"10.1145\/1536414.1536449"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Arora, S., Hazan, E., Kale, S.: 0(sqrt (log n)) approximation to Sparsest Cut in \u00f5(n2) time. In: FOCS: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 238\u2013247 (2004)","DOI":"10.1109\/FOCS.2004.1"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1145\/1250790.1250823","volume-title":"STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing","author":"S. Arora","year":"2007","unstructured":"Arora, S., Kale, S.: A combinatorial, primal-dual approach to semidefinite programs. In: STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 227\u2013236. ACM, New York (2007)"},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1145\/1007352.1007355","volume-title":"STOC 2004: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing","author":"S. Arora","year":"2004","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: STOC 2004: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 222\u2013231. ACM, New York (2004)"},{"key":"2_CR11","unstructured":"Batson, J., Spielman, D.A., Srivastava, N.: Twice-Ramanujan sparsifiers (2008), http:\/\/arxiv.org\/abs\/0808.0163"},{"issue":"1","key":"2_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00211-002-0445-6","volume":"95","author":"M. Bebendorf","year":"2003","unstructured":"Bebendorf, M., Hackbusch, W.: Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L \u2009\u221e\u2009-coefficients. Numerische Mathematik\u00a095(1), 1\u201328 (2003)","journal-title":"Numerische Mathematik"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Approximating s-t minimum cuts in O(n2) time. In: Proceedings of The Twenty-Eighth Annual ACM Symposium on the Theory of Computing, STOC 1996 (1996)","DOI":"10.1145\/237814.237827"},{"issue":"4","key":"2_CR14","doi-asserted-by":"publisher","first-page":"930","DOI":"10.1137\/S0895479801384019","volume":"27","author":"M. Bern","year":"2006","unstructured":"Bern, M., Gilbert, J., Hendrickson, B., Nguyen, N., Toledo, S.: Support-graph preconditioners. SIAM J. Matrix Anal. and Appl.\u00a027(4), 930\u2013951 (2006)","journal-title":"SIAM J. Matrix Anal. and Appl."},{"issue":"3","key":"2_CR15","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1137\/S0895479801390637","volume":"25","author":"E.G. Boman","year":"2003","unstructured":"Boman, E.G., Hendrickson, B.: Support theory for preconditioning. SIAM Journal on Matrix Analysis and Applications\u00a025(3), 694\u2013717 (2003)","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"2_CR16","unstructured":"Boman, E.G., Hendrickson, B., Vavasis, S.: Solving epplitic finite element systems in nearly-linear time with support preconditioners"},{"key":"2_CR17","volume-title":"A Multigrid Tutorial","author":"W.L. Briggs","year":"2001","unstructured":"Briggs, W.L., Henson, V.E., McCormick, S.F.: A Multigrid Tutorial, 2nd edn. SIAM, Philadelphia (2001)","edition":"2"},{"key":"2_CR18","first-page":"195","volume-title":"Problems in Analysis","author":"J. Cheeger","year":"1970","unstructured":"Cheeger, J.: A lower bound for smallest eigenvalue of laplacian. In: Gunning, R.C. (ed.) Problems in Analysis, pp. 195\u2013199. Princeton University Press, Princeton (1970)"},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1145\/10515.10534","volume-title":"SCG 1986: Proceedings of the second annual symposium on Computational geometry","author":"P. Chew","year":"1986","unstructured":"Chew, P.: There is a planar graph almost as good as the complete graph. In: SCG 1986: Proceedings of the second annual symposium on Computational geometry, pp. 169\u2013177. ACM, New York (1986)"},{"key":"2_CR20","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 3rd edn."},{"key":"2_CR21","unstructured":"Daitch, S.I., Spielman, D.A.: Support-graph preconditioners for 2-dimensional trusses"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Daitch, S.I., Spielman, D.A.: Faster approximate lossy generalized flow via interior point algorithms. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 451\u2013460 (2008)","DOI":"10.1145\/1374376.1374441"},{"issue":"2","key":"2_CR23","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1137\/050641661","volume":"32","author":"M. Elkin","year":"2008","unstructured":"Elkin, M., Emek, Y., Spielman, D.A., Teng, S.-H.: Lower-stretch spanning trees. SIAM Journal on Computing\u00a032(2), 608\u2013628 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Frieze, A.M., Miller, G.L., Teng, S.-H.: Separator Based Parallel Divide and Conquer in Computational Geometry. In: SPAA 1992, pp. 420\u2013429 (1992)","DOI":"10.1145\/140901.141934"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/0710032","volume":"10","author":"J.A. George","year":"1973","unstructured":"George, J.A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal.\u00a010, 345\u2013363 (1973)","journal-title":"SIAM J. Numer. Anal."},{"issue":"4","key":"2_CR26","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF01396660","volume":"50","author":"J.R. Gilbert","year":"1987","unstructured":"Gilbert, J.R., Tarjan, R.E.: The analysis of a nested dissection algorithm. Numerische Mathematik\u00a050(4), 377\u2013404 (1987)","journal-title":"Numerische Mathematik"},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/BF01397553","volume":"53","author":"G.H. Golub","year":"1988","unstructured":"Golub, G.H., Overton, M.: The convergence of inexact Chebychev and Richardson iterative methods for solving linear systems. Numerische Mathematik\u00a053, 571\u2013594 (1988)","journal-title":"Numerische Mathematik"},{"key":"2_CR28","unstructured":"Gremban, K.: Combinatorial Preconditioners for Sparse, Symmetric, Diagonall y Dominant Linear Systems. PhD thesis, Carnegie Mellon University, CMU-CS-96-123 (1996)"},{"key":"2_CR29","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1145\/1062745.1062789","volume-title":"WWW 2005: Special interest tracks and posters of the 14th international conference on World Wide Web","author":"A. Gulli","year":"2005","unstructured":"Gulli, A., Signorini, A.: The indexable web is more than 11.5 billion pages. In: WWW 2005: Special interest tracks and posters of the 14th international conference on World Wide Web, pp. 902\u2013903. ACM, New York (2005)"},{"key":"2_CR30","unstructured":"Joshi, A.: Topics in Optimization and Sparse Linear Systems, Ph.D. thesis, UIUC (1997)"},{"key":"2_CR31","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/1132516.1132574","volume-title":"STOC 2006: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing","author":"R. Khandekar","year":"2006","unstructured":"Khandekar, R., Rao, S., Vazirani, U.: Graph partitioning using single commodity flows. In: STOC 2006: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 385\u2013390. ACM, New York (2006)"},{"key":"2_CR32","unstructured":"Kolla, A., Makarychev, Y., Saberi, A., Teng, S.-H.: Subgraph Sparsification. In: STOC 2010 (2010)"},{"key":"2_CR33","unstructured":"Koutis, I., Miller, G., Peng, R.: Approaching optimality for solving SDD systems"},{"key":"2_CR34","doi-asserted-by":"crossref","unstructured":"Koutis, I., Miller, G., Tolliver, D.: Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. In: International Symp. of Visual Computing, pp. 1067\u20131078 (2009)","DOI":"10.1007\/978-3-642-10331-5_99"},{"issue":"2","key":"2_CR35","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM Journal on Numerical Analysis\u00a016(2), 346\u2013358 (1979)","journal-title":"SIAM Journal on Numerical Analysis"},{"issue":"6","key":"2_CR36","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T. Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM\u00a046(6), 787\u2013832 (1999)","journal-title":"Journal of the ACM"},{"key":"2_CR37","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1002\/rsa.3240040402","volume":"4","author":"L. Lovasz","year":"1993","unstructured":"Lovasz, L., Simonovits, M.: Random walks in a convex body and an improved volume algorithm. RSA: Random Structures & Algorithms\u00a04, 359\u2013412 (1993)","journal-title":"RSA: Random Structures & Algorithms"},{"key":"2_CR38","doi-asserted-by":"crossref","unstructured":"Maggs, B., Miller, G., Parekh, O., Ravi, R., Woo, S.M.: Finding effective support-tree preconditioners. In: ACM SPAA, pp. 176\u2013185 (2005)","DOI":"10.1145\/1073970.1073996"},{"key":"2_CR39","doi-asserted-by":"crossref","unstructured":"Madry, A., Kelner, J.: Faster generation of random spanning trees. In: FOCS (2009)","DOI":"10.1109\/FOCS.2009.75"},{"issue":"1","key":"2_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"G.L. Miller","year":"1997","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W.P., Vavasis, S.A.: Separators for sphere-packings and nearest neighbor graphs. J. ACM\u00a044(1), 1\u201329 (1997)","journal-title":"J. ACM"},{"key":"2_CR41","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1145\/1374376.1374442","volume-title":"STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing","author":"L. Orecchia","year":"2008","unstructured":"Orecchia, L., Schulman, L.J., Vazirani, U.V., Vishnoi, N.K.: On partitioning graphs via single commodity flows. In: STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing, pp. 461\u2013470. ACM, New York (2008)"},{"issue":"9","key":"2_CR42","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0898-1221(98)00191-6","volume":"36","author":"J. Rief","year":"1998","unstructured":"Rief, J.: Efficient approximate solution of sparse linear systems. Computer and Mathematics with Applications\u00a036(9), 37\u201358 (1998)","journal-title":"Computer and Mathematics with Applications"},{"key":"2_CR43","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1109\/VR.2002.996525","volume-title":"VR 2002: Proceedings of the IEEE Virtual Reality Conference 2002","author":"A. Sharma","year":"2002","unstructured":"Sharma, A., Liu, X., Miller, P., Nakano, A., Kalia, R.K., Vashishta, P., Zhao, W., Campbell, T.J., Haas, A.: Immersive and interactive exploration of billion-atom systems. In: VR 2002: Proceedings of the IEEE Virtual Reality Conference 2002, p. 217. IEEE Computer Society, Los Alamitos (2002)"},{"issue":"1","key":"2_CR44","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1137\/060650295","volume":"30","author":"G. Shklarski","year":"2008","unstructured":"Shklarski, G., Toledo, S.: Rigidity in finite-element matrices: Sufficient conditions for the rigidity of structures and substructures. SIAM J. Matrix Anal. and Appl.\u00a030(1), 7\u201340 (2008)","journal-title":"SIAM J. Matrix Anal. and Appl."},{"key":"2_CR45","unstructured":"Spielman, D.: Graphs and networks: Random walks and spectral graph drawing. Computer Science, Yale (September 18, 2007), http:\/\/www.cs.yale.edu\/homes\/spielman\/462\/lect4-07.pdf"},{"key":"2_CR46","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. In: Proceedings of the 40th annual ACM Symposium on Theory of Computing, pp. 563\u2013568 (2008)","DOI":"10.1145\/1374376.1374456"},{"key":"2_CR47","doi-asserted-by":"crossref","unstructured":"Spielman, D., Teng, S.-H.: Spectral partitioning works: planar graphs and finite element meshes. In: FOCS 1996: Proceedings of the 37th annual symposium on Foundations of Computer Science, pp. 96\u2013105 (1996)","DOI":"10.1109\/SFCS.1996.548468"},{"key":"2_CR48","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 81\u201390 (2003)","DOI":"10.1145\/1007352.1007372"},{"key":"2_CR49","unstructured":"Spielman, D.A., Teng, S.-H.: A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR, abs\/0809.3232 (2008), http:\/\/arxiv.org\/abs\/0809.3232"},{"key":"2_CR50","unstructured":"Spielman, D.A., Teng, S.-H.: Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105 (2008), http:\/\/www.arxiv.org\/abs\/cs.NA\/0607105"},{"key":"2_CR51","unstructured":"Spielman, D.A., Teng, S.-H.: Spectral sparsification of graphs. CoRR, abs\/0808.4134 (2008), http:\/\/arxiv.org\/abs\/0808.4134"},{"key":"#cr-split#-2_CR52.1","unstructured":"Tolliver, D.A.: Spectral rounding and image segmentation. PhD thesis, Pittsburgh, PA, USA (2006);"},{"key":"#cr-split#-2_CR52.2","unstructured":"Adviser-Miller, G.L., Adviser-Collins, R.T."},{"key":"2_CR53","first-page":"1053","volume-title":"CVPR 2006: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition","author":"D.A. Tolliver","year":"2006","unstructured":"Tolliver, D.A., Miller, G.L.: Graph partitioning by spectral rounding: Applications in image segmentation and clustering. In: CVPR 2006: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 1053\u20131060. IEEE Computer Society, Los Alamitos (2006)"},{"key":"2_CR54","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719574","volume-title":"Numerical Linear Algebra","author":"L.N. Trefethen","year":"1997","unstructured":"Trefethen, L.N., Bau, D.: Numerical Linear Algebra. SIAM, Philadelphia (1997)"},{"key":"2_CR55","unstructured":"Vaidya, P.: Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. An invited at IMA, U. Minnesota (October 1991)"},{"key":"2_CR56","doi-asserted-by":"crossref","unstructured":"Zhou, D., Huang, J., Sch\u00f6lkopf, B.: Learning from Labeled and Unlabeled Data on a Directed Graph. In: The 22nd International Conference on Machine Learning, pp. 1041\u20131048 (2005)","DOI":"10.1145\/1102351.1102482"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13562-0_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:40:03Z","timestamp":1606185603000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13562-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135613","9783642135620"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13562-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}