Optimal Cheeger cuts and bisections of random geometric graphs
From MaRDI portal
Publication:2657914
DOI10.1214/19-AAP1534zbMath1459.05306arXiv1805.08669OpenAlexW2979483613MaRDI QIDQ2657914
Tobias Müller, Mathew D. Penrose
Publication date: 18 March 2021
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.08669
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Geometric probability and stochastic geometry (60D05) Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items (3)
From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds ⋮ Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs ⋮ Rates of convergence for Laplacian semi-supervised learning with low labeling rates
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Continuum limit of total variation on point clouds
- A new approach to Sobolev spaces and connections to \(\Gamma\)-convergence
- An exact combinatorial algorithm for minimum graph bisection
- A framework for solving VLSI graph layout problems
- Minimax grid matching and empirical measures
- Some remarks on uniqueness and regularity of Cheeger sets
- Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
- Approximation of free-discontinuity problems
- The longest edge of the random minimal spanning tree
- On the mixing time of a simple random walk on the super critical percolation cluster
- Consistency of modularity clustering on random geometric graphs
- Spectral gap of random hyperbolic graphs and related parameters
- Vertex ordering and partitioning problems for random spatial graphs.
- Variation and optimization of formes. A geometric analysis
- A nonparametric approach to the estimation of lengths and surface areas
- Approximating Layout Problems on Random Geometric Graphs
- Consistency of Cheeger and Ratio Graph Cuts
- Sets of Finite Perimeter and Geometric Variational Problems
- Topology of random simplicial complexes: a survey
- On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
- Topology and data
- A note on the isoperimetric constant
- A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies
- Random Geometric Graphs
- The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous
- Estimating perimeter using graph cuts
This page was built for publication: Optimal Cheeger cuts and bisections of random geometric graphs
