vertex separator

A Strictly Contractive Peaceman-Rachford Splitting Method for the Doubly Nonnegative Relaxation of the Minimum Cut Problem

  • Xinxin Li
  • Ting Kei Pong
  • Hao Sun
  • Henry Wolkowicz
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , , , , , ,

    The minimum cut problem, MC, and the special case of the vertex separator problem, consists in partitioning the set of nodes of a graph G into k subsets of given sizes in order to minimize the number of edges cut after removing the k-th set. Previous work on this topic uses eigenvalue, semidefinite programming, SDP, … Read more

    The min-cut and vertex separator problem

  • Franz Rendl
  • Renata Sotirov
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We consider graph three-partitions with the objective of minimizing the number of edges between the first two partition sets while keeping the size of the third block small. We review most of the existing relaxations for this min-cut problem and focus on a new class of semidefinite relaxations, based on matrices of order $2n$ which … Read more