Por favor, use este identificador para citar o enlazar este ítem: http://ri.ufs.br/jspui/handle/riufs/1705
Tipo de Documento: Artigo
Título : Polyhedral study of the maximum common induced subgraph problem
Autor : Piva, Breno
Souza, Cid Carvalho de
Fecha de publicación : oct-2012
Resumen : In this paper we present an exact algorithm for the Maximum Common Induced Subgraph Problem (MCIS) by addressing it directly, using Integer Programming (IP) and polyhedral combinatorics. We study the MCIS polytope and introduce strong valid inequalities, some of which we prove to define facets. Besides, we show an equivalence between our IP model for MCIS and a well-known formulation for the Maximum Clique problem. We report on computational results of branch-and-bound (B&B) and branch-and-cut (B&C) algorithms we implemented and compare them to those yielded by an existing combinatorial algorithm.
Palabras clave : Maximum common induced subgraph
Polyhedral combinatorics
Integer programming
Branch and Bound algorithm
Branch and Cut algorithm
Maximum clique
Combinatória poliédrica
Máximo subgrafo comum
Programação linear inteira
Algoritmo Branch and Bound
Algoritmo Branch and Cut
Patrocinio: Financial support by Fapesp, grant number 2007/53617-4 (10/2007 - 02/2009) and CNPq, grants number 132034/2007-7 (03/2007 - 09/2007), 301732/2007-8 and 472504/2007-0.
ISSN : 1572-9338
Institución / Editorial : Springer
Citación : PIVA, B; SOUZA, C. Polyhedral study of the maximum common induced subgraph problem. Annals of Operations Research, v. 199, n. 1, p. 77-102, out. 2012. Disponível em: <http://dx.doi.org/10.1007/s10479-011-1019-8>. Acesso em: 16 mar. 2016.
License: © Springer International Publishing AG - Artigo publicado originalmente em: http://dx.doi.org/10.1007/s10479-011-1019-8
URI : https://ri.ufs.br/handle/riufs/1705
Aparece en las colecciones: DCOMP - Artigos de periódicos

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
PolyhedralStudyProblem.pdf278,17 kBAdobe PDFVista previa
Visualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.