Use este identificador para citar ou linkar para este item: http://ri.ufs.br/jspui/handle/riufs/1705
Tipo de Documento: Artigo
Título: Polyhedral study of the maximum common induced subgraph problem
Autor(es): Piva, Breno
Souza, Cid Carvalho de
Data do documento: Out-2012
Abstract: 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.
Palavras-chave: 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
Agência de fomento: 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
Instituição/Editora: Springer
Citação: 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.
Licença: © 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 nas coleções:DCOMP - Artigos de periódicos

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
PolyhedralStudyProblem.pdf278,17 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.