Use este identificador para citar ou linkar para este item:
https://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 | Tamanho | Formato | |
---|---|---|---|---|
PolyhedralStudyProblem.pdf | 278,17 kB | Adobe PDF | ![]() Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.