Solving the maximum edge-weight clique problem in sparse graphs with compact formulations

This paper studies the behavior of compact formulations for solving the maximum edge-weight clique (MEWC) problem in sparse graphs. The MEWC problem has long been discussed in the literature, but mostly addressing complete graphs, with or without a cardinality constraint on the clique. Yet, several...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Luis Gouveia, Pedro Martins
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2015
Materias:	90C10 90C35 90C90 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/0a6373af69784e349f43270e8714b1ae
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:0a6373af69784e349f43270e8714b1ae
record_format	dspace
spelling	oai:doaj.org-article:0a6373af69784e349f43270e8714b1ae2021-12-02T05:00:42ZSolving the maximum edge-weight clique problem in sparse graphs with compact formulations2192-440610.1007/s13675-014-0028-1https://doaj.org/article/0a6373af69784e349f43270e8714b1ae2015-02-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S219244062100037Xhttps://doaj.org/toc/2192-4406This paper studies the behavior of compact formulations for solving the maximum edge-weight clique (MEWC) problem in sparse graphs. The MEWC problem has long been discussed in the literature, but mostly addressing complete graphs, with or without a cardinality constraint on the clique. Yet, several real-world applications are defined on sparse graphs, where the missing edges are due to some threshold process or because they are not even supposed to be in the graph, at all. Such situations often arise in cell’s metabolic networks, where the amount of metabolites shared among reactions is an important issue to understand the cell’s prevalent elements. We propose new node-discretized formulations for the problem, which are more compact than other models known from the literature. Computational experiments on benchmark and real-world instances are conducted for discussing and comparing the models. These tests indicate that the node-discretized formulations are more efficient for solving large size sparse graphs. Additionally, we also address a new variant of the MEWC problem where the objective to be maximized includes the neighboring edges of the clique.Luis GouveiaPedro MartinsElsevierarticle90C1090C3590C90Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 3, Iss 1, Pp 1-30 (2015)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C10 90C35 90C90 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C10 90C35 90C90 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Luis Gouveia Pedro Martins Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
description	This paper studies the behavior of compact formulations for solving the maximum edge-weight clique (MEWC) problem in sparse graphs. The MEWC problem has long been discussed in the literature, but mostly addressing complete graphs, with or without a cardinality constraint on the clique. Yet, several real-world applications are defined on sparse graphs, where the missing edges are due to some threshold process or because they are not even supposed to be in the graph, at all. Such situations often arise in cell’s metabolic networks, where the amount of metabolites shared among reactions is an important issue to understand the cell’s prevalent elements. We propose new node-discretized formulations for the problem, which are more compact than other models known from the literature. Computational experiments on benchmark and real-world instances are conducted for discussing and comparing the models. These tests indicate that the node-discretized formulations are more efficient for solving large size sparse graphs. Additionally, we also address a new variant of the MEWC problem where the objective to be maximized includes the neighboring edges of the clique.
format	article
author	Luis Gouveia Pedro Martins
author_facet	Luis Gouveia Pedro Martins
author_sort	Luis Gouveia
title	Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
title_short	Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
title_full	Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
title_fullStr	Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
title_full_unstemmed	Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
title_sort	solving the maximum edge-weight clique problem in sparse graphs with compact formulations
publisher	Elsevier
publishDate	2015
url	https://doaj.org/article/0a6373af69784e349f43270e8714b1ae
work_keys_str_mv	AT luisgouveia solvingthemaximumedgeweightcliqueprobleminsparsegraphswithcompactformulations AT pedromartins solvingthemaximumedgeweightcliqueprobleminsparsegraphswithcompactformulations
_version_	1718400811746197504

Solving the maximum edge-weight clique problem in sparse graphs with compact formulations

Ejemplares similares