Spectral concentration and greedy \(k\)-clustering
DOI10.1016/j.comgeo.2018.09.001zbMath1476.68203arXiv1404.1008OpenAlexW2962791199MaRDI QIDQ1624584
Alfred Rossi, Anastasios Sidiropoulos, Pan Peng, Tamal Krishna Dey
Publication date: 16 November 2018
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.1008
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Spectral partitioning works: planar graphs and finite element meshes
- Eigenvalues and expanders
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Spectral Embedding of k-Cliques, Graph Partitioning and k-Means
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
- Testing Cluster Structure of Graphs
- Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
- On clusterings
- How to Round Subspaces: A New Spectral Clustering Algorithm
- Partitioning into Expanders
- Flow-Based Algorithms for Local Graph Clustering
- Multi-way spectral partitioning and higher-order cheeger inequalities
- Many sparse cuts via higher eigenvalues
- Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
- Improved Cheeger's inequality
- Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks
