Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem (Q6080763)

Given a complete weighted graph, the clique partitioning problem (CPP) is to find such a partition of vertices into groups that maximizes the sum of weights of edges connecting vertices within the same groups. The CPP problem is not trivial only when the graph has both positive and negative edge weights. The authors suggest a new method for finding an upper bound on values that the objective function of CPP could reach. They develop the idea proposed by \textit{S. Sobolevsky} et al. [Phys. Rev. E (3) 90, No. 1, Article No. 012811, 8 p. (2014; \url{doi:10.1103/PhysRevE.90.012811})]. Their tactics rely on combining known upper bounds of small subnetworks to calculate the upper bound for the whole network. They describe how to use the upper bounds already available to construct the exact solution of CPP. They also discuss possible directions of further research and show how adding new subnetworks could improve upper bound estimates.