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 / Marinelli, Fabrizio; Pizzuti, Andrea; Rossi, Fabrizio. - ELETTRONICO. - (2019), pp. 119-122. (Intervento presentato al convegno 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2018) tenutosi a Paris, FRANCE nel June 18-20, 2018).
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
