{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:55Z","timestamp":1740109315661,"version":"3.37.3"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,6,25]],"date-time":"2021-06-25T00:00:00Z","timestamp":1624579200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,25]],"date-time":"2021-06-25T00:00:00Z","timestamp":1624579200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s00453-021-00845-4","type":"journal-article","created":{"date-parts":[[2021,6,25]],"date-time":"2021-06-25T11:02:34Z","timestamp":1624618954000},"page":"2859-2894","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Queueing Network-Based Distributed Laplacian Solver"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8656-4023","authenticated-orcid":false,"given":"Iqra Altaf","family":"Gillani","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0694-0602","authenticated-orcid":false,"given":"Amitabha","family":"Bagchi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,25]]},"reference":[{"key":"845_CR1","unstructured":"Aldous, D., Fill, J.: Reversible markov chains and random walks on graphs (2002). (Monograph)"},{"issue":"4","key":"845_CR2","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/0403039","volume":"3","author":"DJ Aldous","year":"1990","unstructured":"Aldous, D.J.: The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discret. Math. 3(4), 450\u2013465 (1990)","journal-title":"SIAM J. Discret. Math."},{"key":"845_CR3","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lov\u00e1sz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: Proceedings of the 20th Annual Symposium on Foundations of Computer Science, SFCS \u201979, pp. 218\u2013223. IEEE Computer Society (1979)","DOI":"10.1109\/SFCS.1979.34"},{"key":"845_CR4","doi-asserted-by":"crossref","unstructured":"Anari, N., Liu, K., Gharan, S.O., Vinzant, C.: Log-concave polynomials IV: Exchange properties, tight mixing times, and faster sampling of spanning trees (2020). ArXiv:2004.07220 [cs.DS]","DOI":"10.1145\/3406325.3451091"},{"key":"845_CR5","doi-asserted-by":"publisher","unstructured":"Andoni, A., Krauthgamer, R., Pogrow, Y.: On Solving Linear Systems in Sublinear Time. In: 10th Innovations in Theoretical Computer Science Conference, ITCS \u201919, vol. 124, pp. 3:1\u20133:19. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2019.3","DOI":"10.4230\/LIPIcs.ITCS.2019.3"},{"key":"845_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Gallager, R.G.: Distributed BFS algorithms. In: Proceedings of the 26th Annual Symp. on Foundations of Computer Science, SFCS \u201985, pp. 250\u2013256. IEEE (1985)","DOI":"10.1109\/SFCS.1985.20"},{"key":"845_CR7","unstructured":"Becchetti, L., Bonifaci, V., Natale, E.: Pooling or sampling: Collective dynamics for electrical flow estimation. In: Proceedings of the 17th Intl. Conf. on Autonomous Agents and MultiAgent Systems, AAMAS \u201918, pp. 1576\u20131584 (2018)"},{"issue":"3","key":"845_CR8","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00224-013-9444-5","volume":"55","author":"GE Blelloch","year":"2014","unstructured":"Blelloch, G.E., Gupta, A., Koutis, I., Miller, G.L., Peng, R., Tangwongsan, K.: Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs. Theory Comput. Syst. 55(3), 521\u2013554 (2014)","journal-title":"Theory Comput. Syst."},{"key":"845_CR9","unstructured":"Boman, E.G., Deweese, K., Gilbert, J.R.: An empirical comparison of graph Laplacian solvers. In: Proceedings of the 18th Workshop on Algorithm Engg. and Experiments, ALENEX \u201916, pp. 174\u2013188. SIAM (2016)"},{"issue":"1","key":"845_CR10","first-page":"95","volume":"40","author":"EG Boman","year":"2016","unstructured":"Boman, E.G., Deweese, K., Gilbert, J.R.: Evaluating the dual randomized Kaczmarz Laplacian linear solver. Informatica 40(1), 95\u2013107 (2016)","journal-title":"Informatica"},{"key":"845_CR11","first-page":"2508","volume":"14","author":"S Boyd","year":"2006","unstructured":"Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE\/ACM Trans. Netw. 14, 2508\u20132530 (2006)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"845_CR12","doi-asserted-by":"crossref","unstructured":"Broder, A.: Generating random spanning trees. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, SFCS \u201989, pp. 442\u2013447. IEEE Computer Society (1989)","DOI":"10.1109\/SFCS.1989.63516"},{"key":"845_CR13","doi-asserted-by":"crossref","unstructured":"Christiano, P., Kelner, J.A., M\u0105dry, A., Spielman, D.A., Teng, S.H.: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In: Proceedings of the 43rd annual ACM Symposium on Theory of computing, STOC \u201911, pp. 273\u2013282. ACM (2011)","DOI":"10.1145\/1993636.1993674"},{"issue":"4\u20135","key":"845_CR14","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1080\/15427951.2015.1009522","volume":"11","author":"F Chung","year":"2015","unstructured":"Chung, F., Simpson, O.: Solving local linear systems with boundary conditions using heat kernel pagerank. Internet Math. 11(4\u20135), 449\u2013471 (2015)","journal-title":"Internet Math."},{"key":"845_CR15","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 46th annual ACM Symposium on Theory of Computing, STOC \u201914, pp. 343\u2013352. ACM (2014)"},{"key":"845_CR16","doi-asserted-by":"crossref","unstructured":"Durfee, D., Kyng, R., Peebles, J., Rao, A.B., Sachdeva, S.: Sampling random spanning trees faster than matrix multiplication. In: Proceedings of the 49th Annual ACM Symposium on Theory of Computing, STOC \u201917, pp. 730\u2013742. ACM (2017)","DOI":"10.1145\/3055399.3055499"},{"issue":"1\u20132","key":"845_CR17","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01159285","volume":"11","author":"L Georgiadis","year":"1992","unstructured":"Georgiadis, L., Szpankowski, W.: Stability of token passing rings. Queue. Syst. 11(1\u20132), 7\u201333 (1992)","journal-title":"Queue. Syst."},{"key":"845_CR18","unstructured":"Ghaffari, M., Haeupler, B.: Brief announcement: Near-optimal BFS-tree construction in radio networks. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC \u201914 (2014)"},{"key":"845_CR19","doi-asserted-by":"crossref","unstructured":"Gillani, I.A., Bagchi, A.: A queueing network-based distributed Laplacian solver. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201920, p. 535\u2013537. ACM (2020)","DOI":"10.1145\/3350755.3400251"},{"key":"845_CR20","doi-asserted-by":"publisher","first-page":"106040","DOI":"10.1016\/j.ipl.2020.106040","volume":"166","author":"IA Gillani","year":"2021","unstructured":"Gillani, I.A., Bagchi, A.: A queueing network-based distributed Laplacian solver for directed graphs. Inf. Proc. Lett. 166, 106040 (2021)","journal-title":"Inf. Proc. Lett."},{"key":"845_CR21","doi-asserted-by":"crossref","unstructured":"Gillani, I.A., Bagchi, A., Ranu, S.: A group-to-group version of random walk betweenness centrality. In: Proceedings of ACM India Joint International Conference on Data Science and Management of Data, CODS-COMAD \u201921, pp. 127\u2013135 (2021)","DOI":"10.1145\/3430984.3431020"},{"key":"845_CR22","unstructured":"Gillani, I.A., Bagchi, A., Vyavahare, P.: A stochastic process on a network with connections to Laplacian systems of equations. Adv. Appl. Probab. (to appear) (2021). Full version: arXiv:1701.05296 [cs.NI]"},{"key":"845_CR23","doi-asserted-by":"publisher","DOI":"10.1002\/9781118625651","volume-title":"Fundamentals of Queueing Theory","author":"D Gross","year":"2008","unstructured":"Gross, D.: Fundamentals of Queueing Theory. John Wiley and Sons, New York (2008)"},{"key":"845_CR24","doi-asserted-by":"crossref","unstructured":"Hoeffding, W.: Probability Inequalities for Sums of Bounded Random Variables. In: Journal of the American Statistical Association, vol.\u00a058, pp. 13\u201330. Taylor and Francis, (1963)","DOI":"10.1080\/01621459.1963.10500830"},{"key":"845_CR25","doi-asserted-by":"crossref","unstructured":"Hoske, D., Lukarski, D., Meyerhenke, H., Wegner, M.: Is nearly-linear the same in theory and practice? a case study with a combinatorial Laplacian solver. In: Proceedings of International Symposium on Experimental Algorithms, SEA \u201915, pp. 205\u2013218. Springer (2015)","DOI":"10.1007\/978-3-319-20086-6_16"},{"key":"845_CR26","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., M\u0105dry, A.: Faster generation of random spanning trees. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201909, pp. 13\u201321. IEEE (2009)","DOI":"10.1109\/FOCS.2009.75"},{"key":"845_CR27","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 45th annual ACM Symposium on Theory of Computing, STOC \u201913, pp. 911\u2013920. ACM (2013)","DOI":"10.1145\/2488608.2488724"},{"key":"845_CR28","doi-asserted-by":"crossref","unstructured":"Konolige, T., Brown, J.: A parallel solver for graph Laplacians. In: Proceedings of the Platform for Advanced Scientific Computing Conf., PASC \u201918, p.\u00a03. ACM (2018)","DOI":"10.1145\/3218176.3218227"},{"key":"845_CR29","unstructured":"Koutis, I., Miller, G.L.: A linear work, $${O}(n^{1\/6})$$ time, parallel algorithm for solving planar Laplacians. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907, pp. 1002\u20131011. SIAM (2007)"},{"key":"845_CR30","doi-asserted-by":"crossref","unstructured":"Koutis, I., Miller, G.L., Peng, R.: A nearly-$$m~ \\log n$$ time solver for SDD linear systems. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS \u201911, pp. 590\u2013598. IEEE (2011)","DOI":"10.1109\/FOCS.2011.85"},{"issue":"12","key":"845_CR31","doi-asserted-by":"publisher","first-page":"1638","DOI":"10.1016\/j.cviu.2011.05.013","volume":"115","author":"I Koutis","year":"2011","unstructured":"Koutis, I., Miller, G.L., Tolliver, D.: Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. Comput. Vision Image Underst. 115(12), 1638\u20131646 (2011)","journal-title":"Comput. Vision Image Underst."},{"key":"845_CR32","doi-asserted-by":"crossref","unstructured":"Kyng, R., Sachdeva, S.: Approximate gaussian elimination for Laplacians-fast, sparse, and simple. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201916, pp. 573\u2013582. IEEE (2016)","DOI":"10.1109\/FOCS.2016.68"},{"issue":"6","key":"845_CR33","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. J. ACM 46(6), 787\u2013832 (1999)","journal-title":"J. ACM"},{"key":"845_CR34","doi-asserted-by":"crossref","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov chains and mixing times. American Mathematical Soc. (2009)","DOI":"10.1090\/mbk\/058"},{"key":"845_CR35","doi-asserted-by":"crossref","unstructured":"Li, H., Peng, R., Shan, L., Yi, Y., Zhang, Z.: Current flow group closeness centrality for complex networks. In: The World Wide Web Conference, WWW \u201919, pp. 961\u2013971. ACM (2019)","DOI":"10.1145\/3308558.3313490"},{"issue":"4","key":"845_CR36","doi-asserted-by":"publisher","first-page":"B499","DOI":"10.1137\/110843563","volume":"34","author":"OE Livne","year":"2012","unstructured":"Livne, O.E., Brandt, A.: Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver. SIAM J. Sci. Comput. 34(4), B499\u2013B522 (2012)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1","key":"845_CR37","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1287\/moor.21.1.182","volume":"21","author":"RB Lund","year":"1996","unstructured":"Lund, R.B., Tweedie, R.L.: Geometric convergence rates for stochastically ordered markov chains. Math. Op. Res. 21(1), 182\u2013194 (1996)","journal-title":"Math. Op. Res."},{"key":"845_CR38","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Peng, R., Xu, S.C.: Parallel graph decompositions using random shifts. In: Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201913, pp. 196\u2013203. ACM (2013)","DOI":"10.1145\/2486159.2486180"},{"key":"845_CR39","doi-asserted-by":"crossref","unstructured":"M\u0105dry, A.: Computing maximum flow with augmenting electrical flows. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201916, pp. 593\u2013602. IEEE (2016)","DOI":"10.1109\/FOCS.2016.70"},{"key":"845_CR40","doi-asserted-by":"crossref","unstructured":"M\u0105dry, A., Straszak, D., Tarnawski, J.: Fast generation of random spanning trees and the effective resistance metric. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201915, pp. 2019\u20132036 (2015)","DOI":"10.1137\/1.9781611973730.134"},{"key":"845_CR41","doi-asserted-by":"crossref","unstructured":"Napov, A., Notay, Y.: An efficient multigrid method for graph Laplacian systems II: robust aggregation. SIAM J. Sci. Comput. 39(5) (2017)","DOI":"10.1137\/16M1071420"},{"key":"845_CR42","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"845_CR43","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 \u201914, pp. 333\u2013342. ACM (2014)","DOI":"10.1145\/2591796.2591832"},{"issue":"36","key":"845_CR44","first-page":"1","volume":"20","author":"P Rebeschini","year":"2019","unstructured":"Rebeschini, P., Tatikonda, S.: A new approach to Laplacian solvers and flow problems. J. Mach. Learn. Res. 20(36), 1\u201337 (2019)","journal-title":"J. Mach. Learn. Res."},{"key":"845_CR45","doi-asserted-by":"crossref","unstructured":"Schild, A.: An almost-linear time algorithm for uniform random spanning tree generation. In: Proceedings of the 50th Annual ACM Symposium on Theory of Computing, STOC \u201918, pp. 214\u2013227. ACM (2018)","DOI":"10.1145\/3188745.3188852"},{"key":"845_CR46","unstructured":"Spielman, D.A.: Laplacians.jl. https:\/\/github.com\/danspielman\/ Laplacians.jl (2017)"},{"issue":"6","key":"845_CR47","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1137\/080734029","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. SIAM J. Comput. 40(6), 1913\u20131926 (2011)","journal-title":"SIAM J. Comput."},{"key":"845_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 36th Annual ACM Symposium on Theory of Computing, STOC \u201904. ACM (2004)","DOI":"10.1145\/1007352.1007372"},{"key":"845_CR49","unstructured":"Tutunov, R.: Fully distributed and mixed symmetric diagonal dominant solvers for large scale optimization (2017). Publicly Accessible Penn. Dissertations"},{"key":"845_CR50","unstructured":"Tutunov, R., Ammar, H.B., Jadbabaie, A.: A fast distributed solver for symmetric diagonally dominant linear equations (2015). ArXiv:1502.03158 [cs.DC]"},{"key":"845_CR51","doi-asserted-by":"crossref","unstructured":"Tutunov, R., El-Zini, J., Bou-Ammar, H., Jadbabaie, A.: Distributed lifelong reinforcement learning with sub-linear regret. In: Proceedings of 56th Annual IEEE Conference on Decision and Control, CDC \u201917, pp. 2254\u20132259. IEEE (2017)","DOI":"10.1109\/CDC.2017.8263978"},{"issue":"1\u20132","key":"845_CR52","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000054","volume":"8","author":"NK Vishnoi","year":"2013","unstructured":"Vishnoi, N.K.: Lx$$=$$ b Laplacian solvers and their algorithmic applications. Found. Trends Theor. Comput. Sci. 8(1\u20132), 1\u2013141 (2013)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"845_CR53","doi-asserted-by":"crossref","unstructured":"Zouzias, A., Freris, N.M.: Randomized gossip algorithms for solving Laplacian systems. In: European Control Conference, ECC \u201915, pp. 1920\u20131925. IEEE (2015)","DOI":"10.1109\/ECC.2015.7330819"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00845-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00845-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00845-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T11:06:19Z","timestamp":1628161579000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00845-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,25]]},"references-count":53,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["845"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00845-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,6,25]]},"assertion":[{"value":"24 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}