This problem is also known as the
*The densest subgraph Problem*

A few references where these instances are used

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.

Each

.datfile 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 jn k nb_non_zero matrix W

W entriesThe optimal solution values are reported here

[1] A. Billionnet, S. Elloumi, A. Lambert and A. Wiegele.

Using a conic bundle method to accelerate both phases of a quadratic convex reformulationInforms 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