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  


[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