New abilities and limitations of spectral graph bisection
From MaRDI portal
Publication:5111755
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 3681933 (Why is no real title available?)
- scientific article; zbMATH DE number 49142 (Why is no real title available?)
- scientific article; zbMATH DE number 1263204 (Why is no real title available?)
- A computational study of graph partitioning
- A framework for solving VLSI graph layout problems
- A polylogarithmic approximation of the minimum bisection
- A spectral heuristic for bisecting random graphs
- A survey of the theory of hypercube graphs
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Algorithms for graph partitioning on the planted partition model
- Algorithms for graph partitioning problems by means of eigenspace relaxations
- Applications of a Planar Separator Theorem
- Approximating the minimum bisection size (extended abstract)
- Approximation algorithms for semi-random partitioning problems
- Coloring Random and Semi-Random k-Colorable Graphs
- Community detection and stochastic block models
- Exact Recovery in the Stochastic Block Model
- Finding k Cuts within Twice the Optimal
- Heuristics for semirandom graph problems
- Hill-climbing finds random planted bisections
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Local convergence of random graph colorings
- Max Cut for Random Graphs with a Planted Partition
- Minimum bisection is fixed parameter tractable
- New abilities and limitations of spectral graph bisection
- On the Quality of Spectral Separators
- Parallel static and dynamic multi‐constraint graph partitioning
- Parameterized graph separation problems
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Semidefinite Programming
- Some simplified NP-complete graph problems
- Spectral methods for graph bisection problems.
- Spectral partitioning works: planar graphs and finite element meshes
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- The ellipsoid method and its consequences in combinatorial optimization
- The solution of some random NP-hard problems in polynomial expected time
Cited in
(6)- On the maximal error of spectral approximation of graph bisection
- New abilities and limitations of spectral graph bisection
- How well do local algorithms solve semidefinite programs?
- A spectral heuristic for bisecting random graphs
- Spectral methods for graph bisection problems.
- scientific article; zbMATH DE number 1696519 (Why is no real title available?)
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)
