Graph Clustering using Effective Resistance
From MaRDI portal
Publication:4993308
DOI10.4230/LIPIcs.ITCS.2018.41zbMath1462.68130arXiv1711.06530OpenAlexW2963643297MaRDI QIDQ4993308
Vedat Levi Alev, Unnamed Author, Nima Anari, Lap Chi Lau
Publication date: 15 June 2021
Full work available at URL: https://arxiv.org/abs/1711.06530
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15)
Related Items (4)
A Spectral Approach to Network Design ⋮ La métrica de resistencia efectiva ⋮ Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis ⋮ Community detection by resistance distance: automation and benchmark testing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Spectral algorithms for unique games
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Covering problems for Brownian motion on spheres
- Low diameter graph decompositions
- The electrical resistance of a graph captures its commute and cover times
- Bounds on the cover time
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
- Spectral Sparsification of Graphs
- The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
- Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
- Approximating unique games
- On clusterings
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- A generalization of permanent inequalities and applications in counting and optimization
- Sampling random spanning trees faster than matrix multiplication
- Approximating Unique Games Using Low Diameter Graph Decomposition
- Faster Generation of Random Spanning Trees
- Higher Eigenvalues of Graphs
- Excluded minors, network decomposition, and multicommodity flow
- Cops, robbers, and threatening skeletons
- Fast Generation of Random Spanning Trees and the Effective Resistance Metric
- Multi-way spectral partitioning and higher-order cheeger inequalities
- Approaching Optimality for Solving SDD Linear Systems
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Min-max Graph Partitioning and Small Set Expansion
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- A Nearly-m log n Time Solver for SDD Linear Systems
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Graph Sparsification by Effective Resistances
This page was built for publication: Graph Clustering using Effective Resistance
