The MIN-cut and vertex separator problem
From MaRDI portal
Publication:683339
DOI10.1007/S10589-017-9943-4zbMATH Open1393.90126OpenAlexW2755613158MaRDI QIDQ683339FDOQ683339
Authors: F. Rendl, Renata Sotirov 
Publication date: 6 February 2018
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10589-017-9943-4
Recommendations
- Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
- A Copositive Programming Approach to Graph Partitioning
- An exact algorithm for solving the vertex separator problem
- The vertex separator problem: a polyhedral investigation
- Graph bisection revisited
Cites Work
- Solving semidefinite-quadratic-linear programs using SDPT3
- Generalized Nested Dissection
- An Efficient Heuristic Procedure for Partitioning Graphs
- Title not available (Why is that?)
- Applications of a Planar Separator Theorem
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- The vertex separator problem: a polyhedral investigation
- A Separator Theorem for Planar Graphs
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Semidefinite programming relaxations for the quadratic assignment problem
- On semidefinite programming relaxations of maximum \(k\)-section
- The vertex separator problem: algorithms and computations
- Lower Bounds for the Partitioning of Graphs
- A framework for solving VLSI graph layout problems
- Title not available (Why is that?)
- Solving large quadratic assignment problems on computational grids
- Partial Lagrangian relaxation for general quadratic programming
- A multilevel bilinear programming algorithm for the vertex separator problem
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- The RPR2 rounding technique for semidefinite programs
- SDP relaxations in combinatorial optimization from a Lagrangian viewpoint.
- A spectral approach to bandwidth and separator problems in graphs
- A Copositive Programming Approach to Graph Partitioning
- Semidefinite programming relaxations for the graph partitioning problem
- A computational study of graph partitioning
- On Lagrangian relaxation of quadratic matrix constraints
- A new bound for the quadratic assignment problem based on convex quadratic programming
- A projection technique for partitioning the nodes of a graph
- An exact algorithm for solving the vertex separator problem
- Geometric Separators for Finite-Element Meshes
- Dual estimates in multiextremal problems
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- Continuous quadratic programming formulations of optimization problems on graphs
- On bounding the bandwidth of graphs with symmetry
- MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING
- Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
Cited In (17)
- Lower bounds for the bandwidth problem
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
- Graph bisection revisited
- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- Title not available (Why is that?)
- A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem
- Continuous quadratic programming formulations of optimization problems on graphs
- A multilevel bilinear programming algorithm for the vertex separator problem
- Two new integer linear programming formulations for the vertex bisection problem
- The complexity of the vertex-minor problem
- Lagrangian Relaxation and Cutting Planes for the Vertex Separator Problem
- Title not available (Why is that?)
- A note on the SDP relaxation of the minimum cut problem
- The vertex separator problem: algorithms and computations
- Partitioning through projections: strong SDP bounds for large graph partition problems
- A new lower bound on the size of the smallest vertex separator of a graph
Uses Software
This page was built for publication: The MIN-cut and vertex separator problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q683339)
