Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
From MaRDI portal
(Redirected from Publication:3580949)
Recommendations
- A linear time algorithm for graph partition problems
- Graph partitioning using linear and semidefinite programming
- scientific article; zbMATH DE number 4062622
- Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition
- Linear time algorithms for finding sparsest cuts in various graph classes
- Approximation Algorithms for Some Graph Partitioning Problems
- A linear time algorithm for determining almost bipartite graphs
- Linear and quadratic programming approaches for the general graph partitioning problem
- Partitioning into degenerate graphs in linear time
- Linear time optimization algorithms for \(P_ 4\)-sparse graphs
Cited in
(only showing first 100 items - show all)- Constructing near spanning trees with few local inspections
- Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
- Global registration of multiple point clouds using semidefinite programming
- Demand-aware network designs of bounded degree
- Modified Cheeger and ratio cut methods using the Ginzburg–Landau functional for classification of high-dimensional data
- A combinatorial cut-toggling algorithm for solving Laplacian linear systems
- The game theoretic p-Laplacian and semi-supervised learning with few labels
- Hardness results for structured linear systems
- Norms of structured random matrices
- A queueing network-based distributed Laplacian solver for directed graphs
- Properly-weighted graph Laplacian for semi-supervised learning
- Learning-augmented maximum flow
- An adaptive fast solver for a general class of positive definite matrices via energy decomposition
- A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
- Persistent Laplacians: properties, algorithms and implications
- A stochastic process on a network with connections to Laplacian systems of equations
- Metric Embedding via Shortest Path Decompositions
- On approximating tree spanners that are breadth first search trees
- The impact of network flows on community formation in models of opinion dynamics
- Bayesian model selection with graph structured sparsity
- Dirichlet eigenvalues, local random walks, and analyzing clusters in graphs
- Random walks and local cuts in graphs
- Engineering a combinatorial Laplacian solver: lessons learned
- Local flow partitioning for faster edge connectivity
- Sparse reliable graph backbones
- Constructing linear-sized spectral sparsification in almost-linear time
- Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems
- Random walks and diffusion on networks
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Minimum cost flow in the CONGEST model
- A general framework for graph sparsification
- Solving graph Laplacian systems through recursive partitioning and two-grid preconditioning
- iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data
- Sparsification of Binary CSPs
- A new approach to Laplacian solvers and flow problems
- The resistance perturbation distance: a metric for the analysis of dynamic networks
- Ranking and sparsifying a connection graph
- Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
- Semi-supervised orthogonal discriminant analysis via label propagation
- Sparsified Cholesky and multigrid solvers for connection Laplacians
- A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
- Efficient approximate solution of sparse linear systems
- Parametric computation of minimum-cost flows with piecewise quadratic costs
- Matrix-free convex optimization modeling
- Sobolev extension by linear operators
- Sparsification of two-variable valued constraint satisfaction problems
- Using petal-decompositions to build a low stretch spanning tree
- On multiplicative \(\lambda\)-approximations and some geometric applications
- Spectrahedral geometry of graph sparsifiers
- Nonobtuse triangulations of PSLGs
- Latent semantic analysis and Fiedler retrieval
- Diagonal of pseudoinverse of graph Laplacian: fast estimation and exact results
- Small-space spectral sparsification via bounded-independence sampling
- Additive sparsification of CSPs
- From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
- Spectral sparsification of graphs
- Improved spectral sparsification and numerical algorithms for SDD matrices
- Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
- A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians
- Approaching optimality for solving SDD linear systems
- Reducing parallel communication in algebraic multigrid through sparsification
- Hardness of graph-structured algebraic and symbolic problems
- Tree spanners of bounded degree graphs
- Contrast invariant SNR and isotonic regressions
- Iteratively reweighted least squares and slime mold dynamics: connection and convergence
- Online row sampling
- A linear time algorithm for graph partition problems
- Training (overparametrized) neural networks in near-linear time
- Perron-Frobenius theory in nearly linear time: positive eigenvectors, M-matrices, graph kernels, and other applications
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- Deterministic approximation of random walks in small space
- Advances in metric embedding theory
- RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
- The approximate duality gap technique: a unified theory of first-order methods
- Nearly-tight bounds for flow sparsifiers in quasi-bipartite graphs
- Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
- Sublinear time hypergraph sparsification via cut and edge sampling queries
- A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
- Hearing the clusters of a graph: A distributed algorithm
- The Small Community Phenomenon in Networks: Models, Algorithms and Applications
- A Nonlinear Algebraic Multigrid Framework for the Power Flow Equations
- Spectral sparsification via bounded-independence sampling
- Fitting a graph to one-dimensional data
- Finding maximum matchings in RDV graphs efficiently
- scientific article; zbMATH DE number 7559046 (Why is no real title available?)
- Sparsification of binary CSPs
- Quantum speedups for linear programming via interior point methods
- Reconstructing Markov processes from independent and anonymous experiments
- A Simple Efficient Interior Point Method for Min-Cost Flow
- Worst-case to expander-case reductions: derandomized and generalized
- Faster min-cost flow and approximate tree decomposition on bounded treewidth graphs
- Practical expander decomposition
- Communities, Random Walks, and Social Sybil Defense
- Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
- Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
- Mean field analysis of personalized PageRank with implications for local graph clustering
- Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
- Better sparsifiers for directed Eulerian graphs
This page was built for publication: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580949)
