k-cluster or densest subgraph Problem Instances

This problem is also known as the The densest subgraph Problem


Problem Description

Files format

The k-cluster instances files

A few references where these instances are used


Problem description

Given a valuated graph G=(V,E) of n nodes and a number k, the problem is to find a subset S of V having a cardinality k and such that the induced subgraph is as dense as possible.



Files format  

Each .dat file contains one instance, in the following format : Number of nodes, k, Number of edges, and then, for any edge [i,j] with i < j wij = 0.5 if and only if an edge links vertices i and j

n k nb_non_zero matrix W
W entries

The optimal solution values are reported here  



The k-cluster instance files  


References

[1] A. Billionnet, S. Elloumi, A. Lambert and A. Wiegele. Using a conic bundle method to accelerate both phases of a quadratic convex reformulation Informs Journal on computing. 29 (2), 318-331 (2017) DOI: 10.1287/ijoc.2016.0731

[2] A. Billionnet , S. Elloumi , M. Plateau - Quadratic Convex Reformulation : a Computational Study of the Graph Bisection Problem, TR CEDRIC No 1003, 2006. (pdf)

[3] A. Billionnet - Different formulations for solving the heaviest k-subgraph problem, Information Systems and Operational Research, vol. 43(3), pp. 171-186, 2005


Back to Main page

Back to SMIQP

Back to Equipe OC

Back to CEDRIC