Abstract: The clique partitioning problem (CPP)is a much-studied and NP-hard combinatorial optimisation problem. We are given a complete undirected graph comprising of nodes and edges that have weights. The task is to partition this graph into subsets (i.e., cliques), such that the sum of the weights of the edges that have both end-vertices in the same subset is maximised. The CPP has many applications in data mining, image processing and structure detection in networks. We propose two new solution methods to this problem. One is a heuristic based on very large scale neighbourhood search and the other is an exact method using cutting-plane techniques. 

 

 

Add to my calendar

Back to listing

<October 2017>
Mo Tu We Th Fr Sa Su
25262728293001
02030405060708
09101112131415
16171819202122
23242526272829
30310102030405