Graph bisection revisited
From MaRDI portal
Abstract: The graph bisection problem is the problem of partitioning the vertex set of a graph into two sets of given sizes such that the sum of weights of edges joining these two sets is optimized. We present a semidefinite programming relaxation for the graph bisection problem with a matrix variable of order - the number of vertices of the graph - that is equivalent to the currently strongest semidefinite programming relaxation obtained by using vector lifting. The reduction in the size of the matrix variable enables us to impose additional valid inequalities to the relaxation in order to further strengthen it. The numerical results confirm that our simplified and strengthened semidefinite relaxation provides the currently strongest bound for the graph bisection problem in reasonable time.
Recommendations
- Bisections of graphs
- On the graph bisection problem
- scientific article; zbMATH DE number 1817784
- On bisections of directed graphs
- Better Bounds for Graph Bisection
- On judicious bisections of graphs
- Bisplit graphs
- Bipartization of graphs
- On the bipartition of graphs
- On the Graph Bisection Cut Polytope
Cites work
- scientific article; zbMATH DE number 49142 (Why is no real title available?)
- scientific article; zbMATH DE number 2196287 (Why is no real title available?)
- A new approach to minimising the frontwidth in finite element calculations
- An efficient semidefinite programming relaxation for the graph partition problem
- An improved rounding method and semidefinite programming relaxation for graph partition
- Approximation algorithms for maximization problems arising in graph partitioning
- Clustering of high throughput gene expression data
- Graph partitioning and parallel computing
- Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
- Min-cut clustering
- Multiple-way network partitioning
- On semidefinite programming relaxations of maximum \(k\)-section
- Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing
- Relaxations of combinatorial problems via association schemes
- SDP relaxations for some combinatorial optimization problems
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- Semidefinite programming relaxations for the graph partitioning problem
- Solving Graph Bisection Problems with Semidefinite Programming
- Some simplified NP-complete graph problems
- Tabu search for graph partitioning
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- The MIN-cut and vertex separator problem
- The node capacitated graph partitioning problem: A computational study
Cited in
(18)- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- scientific article; zbMATH DE number 1778391 (Why is no real title available?)
- The MIN-cut and vertex separator problem
- Applications of the Dulmage--Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement
- Solving Graph Bisection Problems with Semidefinite Programming
- scientific article; zbMATH DE number 1333614 (Why is no real title available?)
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- Better Bounds for Graph Bisection
- A semidefinite relaxation based global algorithm for two-level graph partition problem
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
- Bisection width of transposition graphs
- On semidefinite programming relaxations of maximum \(k\)-section
- A semidefinite programming approach to the hypergraph minimum bisection problem
- scientific article; zbMATH DE number 1817784 (Why is no real title available?)
- An efficient semidefinite programming relaxation for the graph partition problem
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- Partitioning through projections: strong SDP bounds for large graph partition problems
This page was built for publication: Graph bisection revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1657405)
