scientific article; zbMATH DE number 7205044
From MaRDI portal
Publication:5111755
DOI10.4230/LIPICS.ESA.2017.66zbMath1442.68184arXiv1701.01337MaRDI QIDQ5111755
Maciej Liśkiewicz, Martin Schuster
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1701.01337
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms (68W40) Convex programming (90C25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Consistency thresholds for the planted bisection model
- A framework for solving VLSI graph layout problems
- Parameterized graph separation problems
- Spectral partitioning works: planar graphs and finite element meshes
- A survey of the theory of hypercube graphs
- The ellipsoid method and its consequences in combinatorial optimization
- Some simplified NP-complete graph problems
- A computational study of graph partitioning
- Spectral methods for graph bisection problems.
- Algorithms for graph partitioning problems by means of eigenspace relaxations
- Heuristics for semirandom graph problems
- A Polylogarithmic Approximation of the Minimum Bisection
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Exact Recovery in the Stochastic Block Model
- The solution of some random NP-hard problems in polynomial expected time
- Approximating the minimum bisection size (extended abstract)
- Applications of a Planar Separator Theorem
- Finding k Cuts within Twice the Optimal
- On the Quality of Spectral Separators
- Parallel static and dynamic multi‐constraint graph partitioning
- Community Detection and Stochastic Block Models
- Max Cut for Random Graphs with a Planted Partition
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Coloring Random and Semi-Random k-Colorable Graphs
- Semidefinite Programming
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- Minimum bisection is fixed parameter tractable
- Local Convergence of Random Graph Colorings
- Approximation algorithms for semi-random partitioning problems
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
This page was built for publication:
