Given a simple and undirected graph, the maximum γ-quasi-clique problem consists in identifying the induced subgraph of maximum order and edge density of at least γ. In this paper we propose a new extended formulation for such a problem obtained by decomposing star inequalities. Preliminary computational results assess the quality of the continuous relaxation with respect to the tightest formulation available in the literature.
A star-based reformulation for the maximum quasi-clique problem
Fabrizio Marinelli
;Andrea Pizzuti;
2019-01-01
Abstract
Given a simple and undirected graph, the maximum γ-quasi-clique problem consists in identifying the induced subgraph of maximum order and edge density of at least γ. In this paper we propose a new extended formulation for such a problem obtained by decomposing star inequalities. Preliminary computational results assess the quality of the continuous relaxation with respect to the tightest formulation available in the literature.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
