Bonato, Dr. Thorsten

The max-cut problem is an NP-hard combinatorial optimization problem defined on undirected weighted graphs. It consists in finding a subset of the graph's nodes such that the aggregate weight of the edges between the subset and its complement is maximized. This book deals with a new separation approach to be used within a branch-and-cut algorithm for solving max-cut problems to optimality. The method is based on graph contraction and allows the fast separation of so-called odd-cycle inequalities. In addition, we...