A New Global Algorithm for Max-Cut Problem with Chordal Sparsity
Lu, C., Deng, Z., Fang, S.-C., & Xing, W. (2023, March 20). JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS.
author keywords: Max-cut; Branch-and-bound; Sparsity pattern
TL;DR:
A semidefinite relaxation-based branch-and-bound algorithm that exploits the chordal sparsity patterns of the max-cut problem and proposes a new branching rule called hierarchy branching rule, which utilizes the tree decomposition of the sparsity pattern.
(via
Semantic Scholar)