{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T04:44:47Z","timestamp":1768106687881,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"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":["Algorithmica"],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s00453-023-01154-8","type":"journal-article","created":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T11:01:53Z","timestamp":1690887713000},"page":"3680-3716","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems"],"prefix":"10.1007","volume":"85","author":[{"given":"Monika","family":"Henzinger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Billy","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,1]]},"reference":[{"key":"1154_CR1","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 36th Annual ACM Symposium on the Theory of Computing, pp. 81\u201390 (2004)","DOI":"10.1145\/1007352.1007372"},{"key":"1154_CR2","doi-asserted-by":"publisher","unstructured":"Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., Sachdeva, S.: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time (2022). https:\/\/doi.org\/10.48550\/ARXIV.2203.00671. arXiv:2203.00671","DOI":"10.48550\/ARXIV.2203.00671"},{"key":"1154_CR3","doi-asserted-by":"crossref","unstructured":"Christiano, P., Kelner, J.A., M\u0105dry, A., Spielman, D., Teng, S.-H.: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In: Proceedings of the 42nd Annual ACM Symposium on the Theory of Computing, pp. 273\u2013282 (2011)","DOI":"10.1145\/1993636.1993674"},{"key":"1154_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/20M1383525","author":"T Kathuria","year":"2022","unstructured":"Kathuria, T., Liu, Y.P., Sidford, A.: Unit capacity maxflow in almost $$m^{4\/3}$$ time. SIAM J. Comput. (2022). https:\/\/doi.org\/10.1137\/20M1383525","journal-title":"SIAM J. Comput."},{"key":"1154_CR5","doi-asserted-by":"crossref","unstructured":"M\u0105dry, A.: Computing maximum flow with augmenting electrical flows. In: Proceedings of the 57th IEEE Symposium on the Foundations of Computer Science, pp. 593\u2013602 (2016)","DOI":"10.1109\/FOCS.2016.70"},{"key":"1154_CR6","doi-asserted-by":"publisher","unstructured":"Gao, Y., Liu, Y.P., Peng, R.: Fully dynamic electrical flows: sparse maxflow faster than Goldberg-Rao. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 516\u2013527 (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00058","DOI":"10.1109\/FOCS52979.2021.00058"},{"key":"1154_CR7","doi-asserted-by":"publisher","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 45th Annual ACM Symposium on the Theory of Computing, pp. 911\u2013920 (2013). https:\/\/doi.org\/10.1145\/2488608.2488724","DOI":"10.1145\/2488608.2488724"},{"key":"1154_CR8","unstructured":"Boman, E.G., Deweese, K., Gilbert, J.R.: Evaluating the potential of a dual randomized Kaczmarz Laplacian linear solver. Informatica 40, 95\u2013107 (2016)"},{"key":"1154_CR9","doi-asserted-by":"crossref","unstructured":"Boman, E.G., Deweese, K., Gilbert, J.R.: An empirical comparison of graph Laplacian solvers. In: Proceedings of the 18th Workshop on Algorithm Engineering and Experiments, pp. 174\u2013188 (2016)","DOI":"10.1137\/1.9781611974317.15"},{"key":"1154_CR10","doi-asserted-by":"crossref","unstructured":"Deweese, K., Gilbert, J.R., Miller, G., Peng, R., Xu, H., Xu, S.: An empirical study of cycle toggling based Laplacian solvers. In: Proceedings of the 7th SIAM Workshop on Combinatorial Scientific Computing, pp. 33\u201341 (2016)","DOI":"10.1137\/1.9781611974690.ch4"},{"key":"1154_CR11","doi-asserted-by":"crossref","unstructured":"Hoske, D., Lukarski, D., Meyerhenke, H., Wegner, M.: Engineering a combinatorial Laplacian solver: Lessons learned. Algorithms 9 (2016). Article 72","DOI":"10.3390\/a9040072"},{"key":"1154_CR12","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1145\/76359.76368","volume":"36","author":"AV Goldberg","year":"1989","unstructured":"Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by canceling negative cycles. J. ACM 36, 873\u2013886 (1989)","journal-title":"J. ACM"},{"key":"1154_CR13","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0166-218X(93)90025-J","volume":"46","author":"TR Ervolina","year":"1993","unstructured":"Ervolina, T.R., McCormick, S.T.: Two strongly polynomial cut cancelling algorithms for minimum cost network flow. Discrete Appl. Math. 46, 133\u2013165 (1993)","journal-title":"Discrete Appl. Math."},{"key":"1154_CR14","doi-asserted-by":"publisher","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D., Saranurak, T.: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: Proceedings of the 47th Annual ACM Symposium on the Theory of Computing, pp. 21\u201330 (2015). https:\/\/doi.org\/10.1145\/2746539.2746609","DOI":"10.1145\/2746539.2746609"},{"key":"1154_CR15","unstructured":"Sherman, J.: Personal communication (2017)"},{"key":"1154_CR16","doi-asserted-by":"publisher","unstructured":"Kyng, R., Pachocki, J., Peng, R., Sachdeva, S.: A framework for analyzing resparsification algorithms. In: Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2032\u20132043 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.132","DOI":"10.1137\/1.9781611974782.132"},{"issue":"8","key":"1154_CR17","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/2492007.2492029","volume":"56","author":"JD Batson","year":"2013","unstructured":"Batson, J.D., Spielman, D.A., Srivastava, N., Teng, S.: Spectral sparsification of graphs: theory and algorithms. Commun. ACM 56(8), 87\u201394 (2013)","journal-title":"Commun. ACM"},{"key":"1154_CR18","doi-asserted-by":"publisher","unstructured":"Abraham, I., Neiman, O.: Using petal-decompositions to build a low stretch spanning tree. In: Proceedings of the 44th Symposium on the Theory of Computing, pp. 395\u2013406 (2012). https:\/\/doi.org\/10.1145\/2213977.2214015","DOI":"10.1145\/2213977.2214015"},{"key":"1154_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/9781316888568","volume-title":"Network Flow Algorithms","author":"DP Williamson","year":"2019","unstructured":"Williamson, D.P.: Network Flow Algorithms. Cambridge University Press, Cambridge (2019)"},{"issue":"3","key":"1154_CR20","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983). https:\/\/doi.org\/10.1016\/0022-0000(83)90006-5","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1154_CR21","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"DR Karger","year":"2000","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. J. ACM 47(1), 46\u201376 (2000). https:\/\/doi.org\/10.1145\/331605.331608","journal-title":"J. ACM"},{"issue":"10","key":"1154_CR22","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/2347736.2347759","volume":"55","author":"I Koutis","year":"2012","unstructured":"Koutis, I., Miller, G.L., Peng, R.: A fast solver for a class of linear systems. Commun. ACM 55(10), 99\u2013107 (2012). https:\/\/doi.org\/10.1145\/2347736.2347759","journal-title":"Commun. ACM"},{"key":"1154_CR23","doi-asserted-by":"crossref","unstructured":"Jambulapati, A., Sidford, A.: Ultrasparse ultrasparsifiers and faster laplacian system solvers. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, pp. 540\u2013559. SIAM (2021). arXiv:2011.08806","DOI":"10.1137\/1.9781611976465.33"},{"key":"1154_CR24","unstructured":"Cohen, M.B., Kyng, R., Miller, G.L., Pachocki, J.W., Peng, R., Rao, A.B., Xu, S.C.: Solving SDD linear systems in nearly $$m \\log ^{1\/2} n$$ time. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pp. 343\u2013352 (2014)"},{"key":"1154_CR25","doi-asserted-by":"publisher","DOI":"10.1145\/2948062","author":"I Koutis","year":"2016","unstructured":"Koutis, I., Xu, S.C.: Simple parallel and distributed algorithms for spectral graph sparsification. ACM Trans. Parallel Comput. (2016). https:\/\/doi.org\/10.1145\/2948062","journal-title":"ACM Trans. Parallel Comput."},{"issue":"4","key":"1154_CR26","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1137\/08074489X","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Teng, S.: Spectral sparsification of graphs. SIAM J. Comput. 40(4), 981\u20131025 (2011). arXiv:0808.4134","journal-title":"SIAM J. Comput."},{"key":"1154_CR27","doi-asserted-by":"publisher","unstructured":"Kapralov, M., Panigrahy, R.: Spectral sparsification via random spanners. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. ITCS \u201912, pp. 393\u2013398. Association for Computing Machinery, New York, NY, USA (2012). https:\/\/doi.org\/10.1145\/2090236.2090267","DOI":"10.1145\/2090236.2090267"},{"key":"1154_CR28","doi-asserted-by":"crossref","unstructured":"Peng, R., Spielman, D.A.: An Efficient Parallel Solver for SDD Linear Systems (2013)","DOI":"10.1145\/2591796.2591832"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01154-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01154-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01154-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T13:09:00Z","timestamp":1729861740000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01154-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,1]]},"references-count":28,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1154"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01154-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,1]]},"assertion":[{"value":"13 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}