The MIN-cut and vertex separator problem

DOI10.1007/s10589-017-9943-4zbMath1393.90126OpenAlexW2755613158MaRDI QIDQ683339

Renata Sotirov, Fanz Rendl

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

zbMATH Keywords

semidefinite programmingminimum cutconvexificationvertex separator

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22)

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

• SDPT3
• MatrixMarket

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