New abilities and limitations of spectral graph bisection
DOI10.4230/LIPICS.ESA.2017.66zbMATH Open1442.68184arXiv1701.01337MaRDI QIDQ5111755FDOQ5111755
Authors: Martin Schuster, Maciej Liśkiewicz 
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1701.01337
Recommendations
Convex programming (90C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Semidefinite Programming
- Exact Recovery in the Stochastic Block Model
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Consistency thresholds for the planted bisection model
- Applications of a Planar Separator Theorem
- The ellipsoid method and its consequences in combinatorial optimization
- Title not available (Why is that?)
- Parameterized graph separation problems
- Some simplified NP-complete graph problems
- A survey of the theory of hypercube graphs
- A spectral heuristic for bisecting random graphs
- Title not available (Why is that?)
- The solution of some random NP-hard problems in polynomial expected time
- Algorithms for graph partitioning on the planted partition model
- Title not available (Why is that?)
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- A framework for solving VLSI graph layout problems
- Spectral partitioning works: planar graphs and finite element meshes
- Finding k Cuts within Twice the Optimal
- A computational study of graph partitioning
- Parallel static and dynamic multi‐constraint graph partitioning
- A polylogarithmic approximation of the minimum bisection
- On the Quality of Spectral Separators
- Minimum bisection is fixed parameter tractable
- Community detection and stochastic block models
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Heuristics for semirandom graph problems
- Coloring Random and Semi-Random k-Colorable Graphs
- Approximation algorithms for semi-random partitioning problems
- Spectral methods for graph bisection problems.
- New abilities and limitations of spectral graph bisection
- Algorithms for graph partitioning problems by means of eigenspace relaxations
- Approximating the minimum bisection size (extended abstract)
- Local convergence of random graph colorings
- Hill-climbing finds random planted bisections
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- Max Cut for Random Graphs with a Planted Partition
Cited In (6)
- How well do local algorithms solve semidefinite programs?
- Spectral methods for graph bisection problems.
- New abilities and limitations of spectral graph bisection
- Title not available (Why is that?)
- On the maximal error of spectral approximation of graph bisection
- A spectral heuristic for bisecting random graphs
This page was built for publication: New abilities and limitations of spectral graph bisection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111755)
