{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T16:12:39Z","timestamp":1743091959788,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319200859"},{"type":"electronic","value":"9783319200866"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-20086-6_16","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T08:27:10Z","timestamp":1434702430000},"page":"205-218","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Is Nearly-linear the Same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Hoske","sequence":"first","affiliation":[]},{"given":"Dimitar","family":"Lukarski","sequence":"additional","affiliation":[]},{"given":"Henning","family":"Meyerhenke","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Wegner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Nearly tight low stretch spanning trees. In: 49th Annual Symposium on Foundations of Computer Science, pp. 781\u2013790 (2008)","DOI":"10.1109\/FOCS.2008.62"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Neiman, O.: Using petal-decompositions to build a low stretch spanning tree. In: 44th ACM Symposium on Theory of Computing, pp. 395\u2013406 (2012)","DOI":"10.1145\/2213977.2214015"},{"key":"16_CR3","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 24, 78\u2013100 (1995)","journal-title":"SIAM Journal on Computing"},{"issue":"5439","key":"16_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A-L Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"issue":"6","key":"16_CR5","doi-asserted-by":"publisher","first-page":"3264","DOI":"10.1137\/040611781","volume":"46","author":"E Boman","year":"2008","unstructured":"Boman, E., Hendrickson, B., Vavasis, S.: Solving elliptic finite element systems in near-linear time with support preconditioners. SIAM Journal on Numerical Analysis 46(6), 3264\u20133284 (2008)","journal-title":"SIAM Journal on Numerical Analysis"},{"key":"16_CR6","unstructured":"Briggs, W.L., Henson, V.E., McCormick, S.F.: A multigrid tutorial. SIAM (2000)"},{"issue":"3","key":"16_CR7","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1177\/109434200001400303","volume":"14","author":"S Browne","year":"2000","unstructured":"Browne, S., Dongarra, J., Garner, N., Ho, G., Mucci, P.: A portable programming interface for performance evaluation on modern processors. Int. J. High Perform. Comput. Appl. 14(3), 189\u2013204 (2000)","journal-title":"Int. J. High Perform. Comput. Appl."},{"key":"16_CR8","doi-asserted-by":"crossref","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: Proc. 43rd ACM Symp. on Theory of Computing (STOC), pp. 273\u2013282. ACM (2011)","DOI":"10.1145\/1993636.1993674"},{"key":"16_CR9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971446","volume-title":"Applied Numerical Linear Algebra","author":"JW Demmel","year":"1997","unstructured":"Demmel, J.W.: Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia (1997)"},{"issue":"7","key":"16_CR10","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0167-8191(99)00018-6","volume":"25","author":"R Diekmann","year":"1999","unstructured":"Diekmann, R., Frommer, A., Monien, B.: Efficient schemes for nearest neighbor load balancing. Parallel Computing 25(7), 789\u2013812 (1999)","journal-title":"Parallel Computing"},{"key":"16_CR11","doi-asserted-by":"crossref","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, New York, NY, USA, pp. 494\u2013503. ACM (2005)","DOI":"10.1145\/1060590.1060665"},{"key":"16_CR12","unstructured":"Guennebaud, G., Jacob, B., et al.: Eigen v3 (2010). http:\/\/eigen.tuxfamily.org"},{"key":"16_CR13","unstructured":"Hoske, D.: An experimental study of a nearly-linear time Laplacian solver. Master\u2019s thesis, Karlsruhe Institute of Technology (KIT) (2014)"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., Orecchia, L., Sidford, A., Zhu, Z.A.: A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp. 911\u2013920 (2013)","DOI":"10.1145\/2488608.2488724"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Koutis, I.: Simple parallel and distributed algorithms for spectral graph sparsification. In: Proc. 26th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 61\u201366. ACM (2014)","DOI":"10.1145\/2612669.2612676"},{"key":"16_CR16","unstructured":"Koutis, I., Levin, A., Peng, R.: Improved spectral sparsification and numerical algorithms for SDD matrices. In: Symposium on Theoretical Aspects of Computer Science, vol. 14, pp. 266\u2013277 (2012)"},{"key":"16_CR17","unstructured":"Lukarski, D.: Paralution - library for iterative sparse methods (2015). http:\/\/www.paralution.com (last accessed February 09, 2015)"},{"issue":"2","key":"16_CR18","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0111030","volume":"11","author":"D Marquardt","year":"1963","unstructured":"Marquardt, D.: An algorithm for least-squares estimation of nonlinear parameters. Journal of the Society for Industrial and Applied Mathematics 11(2), 431\u2013441 (1963)","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"16_CR19","unstructured":"Papp, P.A.: Low-Stretch Spanning Trees. Bachelor thesis, E\u00f6tv\u00f6s Lor\u00e1nd University (2014)"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"Peng, R., Spielman, D.A.: An efficient parallel solver for SDD linear systems. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC 2014, New York, NY, USA, pp. 333\u2013342. ACM (2014)","DOI":"10.1145\/2591796.2591832"},{"issue":"9","key":"16_CR21","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0898-1221(98)00191-6","volume":"36","author":"JH Reif","year":"1998","unstructured":"Reif, J.H.: Efficient approximate solution of sparse linear systems. Computers & Mathematics with Applications 36(9), 37\u201358 (1998)","journal-title":"Computers & Mathematics with Applications"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. In: STOC 2008, New York, NY, USA (2008)","DOI":"10.1145\/1374376.1374456"},{"key":"16_CR23","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: STOC 2004, New York, NY, USA, pp. 81\u201390 (2004)","DOI":"10.1145\/1007352.1007372"},{"key":"16_CR24","unstructured":"Spielman, D.A., Woo, J.: A note on preconditioning by low-stretch spanning trees. CoRR, abs\/0903.2816 (2009)"},{"key":"16_CR25","unstructured":"Staudt, C.L., Sazonovs, A., Meyerhenke, H.: NetworKit: An interactive tool suite for high-performance network analysis. arXiv:1403.3005 (2014)"},{"key":"16_CR26","unstructured":"Vaidya, P.M.: Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Technical report, University of Illinois at Urbana-Champaign, Urbana, IL (1990)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-20086-6_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T21:51:15Z","timestamp":1676584275000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-20086-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319200859","9783319200866"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-20086-6_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}