Please use this identifier to cite or link to this item:
Document Type: Artigo
Title: Polyhedral study of the maximum common induced subgraph problem
Authors: Piva, Breno
Souza, Cid Carvalho de
Issue Date: Oct-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.
Keywords: 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
Sponsorship: 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
Publisher / Institution : Springer
Citation: 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: <>. Acesso em: 16 mar. 2016.
License: © Springer International Publishing AG - Artigo publicado originalmente em:
Appears in Collections:DCOMP - Artigos de periódicos

Files in This Item:
File Description SizeFormat 
PolyhedralStudyProblem.pdf278,17 kBAdobe PDFThumbnail

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.