The MIN-cut and vertex separator problem
From MaRDI portal
Publication:683339
DOI10.1007/s10589-017-9943-4zbMath1393.90126OpenAlexW2755613158MaRDI QIDQ683339
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
Related Items (9)
Graph bisection revisited ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ Lower bounds for the bandwidth problem ⋮ Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs ⋮ A note on the SDP relaxation of the minimum cut problem ⋮ Partitioning through projections: strong SDP bounds for large graph partition problems ⋮ A multilevel bilinear programming algorithm for the vertex separator problem ⋮ A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem ⋮ Two new integer linear programming formulations for the vertex bisection problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solving semidefinite-quadratic-linear programs using SDPT3
- An exact algorithm for solving the vertex separator problem
- A multilevel bilinear programming algorithm for the vertex separator problem
- A framework for solving VLSI graph layout problems
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Dual estimates in multiextremal problems
- A computational study of graph partitioning
- Semidefinite programming relaxations for the quadratic assignment problem
- Solving large quadratic assignment problems on computational grids
- A projection technique for partitioning the nodes of a graph
- On semidefinite programming relaxations of maximum \(k\)-section
- Semidefinite programming relaxations for the graph partitioning problem
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- The vertex separator problem: algorithms and computations
- The vertex separator problem: a polyhedral investigation
- Continuous quadratic programming formulations of optimization problems on graphs
- Partial Lagrangian relaxation for general quadratic programming
- On Lagrangian Relaxation of Quadratic Matrix Constraints
- On Bounding the Bandwidth of Graphs with Symmetry
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING
- A Separator Theorem for Planar Graphs
- Generalized Nested Dissection
- Applications of a Planar Separator Theorem
- An Efficient Heuristic Procedure for Partitioning Graphs
- Geometric Separators for Finite-Element Meshes
- A spectral approach to bandwidth and separator problems in graphs
- A Copositive Programming Approach to Graph Partitioning
- The RPR2 rounding technique for semidefinite programs
- Lower Bounds for the Partitioning of Graphs
- A new bound for the quadratic assignment problem based on convex quadratic programming
- Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
This page was built for publication: The MIN-cut and vertex separator problem