Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
From MaRDI portal
Publication:5002784
DOI10.4230/LIPIcs.ICALP.2018.101zbMath1499.68285arXiv1805.09747OpenAlexW2963363792MaRDI QIDQ5002784
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1805.09747
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Consistency thresholds for the planted bisection model
- Community detection in sparse networks via Grothendieck's inequality
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Eigenvalues and expanders
- The Metropolis algorithm for graph bisection
- Heuristics for semirandom graph problems
- Graph expansion and the unique games conjecture
- Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Exact Recovery in the Stochastic Block Model
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
- Constant factor approximation for balanced cut in the PIE model
- Community detection thresholds and the weak Ramanujan property
- How robust are reconstruction thresholds for community detection?
- Approximation algorithms for semi-random partitioning problems
- Colouring Semirandom Graphs
- Expander flows, geometric embeddings and graph partitioning
- \(\lambda_{\infty}\), vertex isoperimetry and concentration
This page was built for publication: Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
