|
 
|
[Bil05c] Different formulations for solving the heaviest k-subgraph problem
Revue Internationale avec comité de lecture : Journal INFOR, vol. 43(3), pp. 171-186, 2005Mots clés: Heaviest k-subgraph problem, mixed-integer linear programming, upper bounds, experiments.
Résumé:
We consider the heaviest k-subgraph problem (HSP), 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. The aim of the paper is to show what can be expected from mixed-integer linear programming for solving this problem. We compare from a theoretical and practical point of view different MIP formulations of HSP. Computational experiments when the weight of each edge is equal to 1 are reported. They show that the MIP approach is particularly efficient for dense instances.
Equipe:
oc
BibTeX
| @article { | |||
| Bil05c, | |||
| title | = | "{Different formulations for solving the heaviest k-subgraph problem}", | |
| author | = | "A. Billionnet", | |
| journal | = | "INFOR", | |
| year | = | 2005, | |
| volume | = | 43, | |
| number | = | 3, | |
| pages | = | "171-186", | |
| } | |||
