A combinatorial cut-toggling algorithm for solving Laplacian linear systems
From MaRDI portal
Publication:6066766
DOI10.1007/s00453-023-01154-8arXiv2010.16316MaRDI QIDQ6066766
David P. Williamson, Billy Jin, Monika R. Henzinger, Richard Peng
Publication date: 13 December 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2010.16316
Cites Work
- Two strongly polynomial cut cancelling algorithms for minimum cost network flow
- Engineering a combinatorial Laplacian solver: lessons learned
- A data structure for dynamic trees
- Spectral sparsification via random spanners
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Spectral Sparsification of Graphs
- Finding minimum-cost circulations by canceling negative cycles
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- A Framework for Analyzing Resparsification Algorithms
- Unit Capacity Maxflow in Almost $m^{4/3}$ Time
- An Empirical Comparison of Graph Laplacian Solvers
- An efficient parallel solver for SDD linear systems
- Solving SDD linear systems in nearly m log 1/2 n time
- Network Flow Algorithms
- Using petal-decompositions to build a low stretch spanning tree
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Minimum cuts in near-linear time
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
This page was built for publication: A combinatorial cut-toggling algorithm for solving Laplacian linear systems
