|
 
|
[BIL02b] Different formulations for the heaviest k-subgraph problem
Rapport Scientifique : Date de dépot: 2002/01/01, (Tech. Rep.: CEDRIC-02-384)
motcle:
Résumé:
We consider the heaviest subgraph problem, i.e. determine a block of k nodes of a weighted graph (of n nodes) such that the total edge weight within the subgraph induced by the block is maximized. We compare from a theoretical and practical point of view different mixed integer programming formulations of this problem. Computational experiments when the weight of each edge is equal to 1 are reported.
Key words: Heaviest k-subgraph problem, mixed integer linear programming, upper bounds, experiments.
BibTeX
| @techreport { | |||
| BIL02b, | |||
| title | = | "{Different formulations for the heaviest k-subgraph problem}", | |
| author | = | "A. Billionnet", | |
| number | = | "{CEDRIC-02-384}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {01-01-2002}, | |
| } | |||
