Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorPiva, Breno-
dc.contributor.authorSouza, Cid Carvalho de-
dc.identifier.citationPIVA, 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.pt_BR
dc.description.abstractIn 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.pt_BR
dc.description.sponsorshipFinancial 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.pt_BR
dc.subjectMaximum common induced subgraphpt_BR
dc.subjectPolyhedral combinatoricspt_BR
dc.subjectInteger programmingpt_BR
dc.subjectBranch and Bound algorithmpt_BR
dc.subjectBranch and Cut algorithmpt_BR
dc.subjectMaximum cliquept_BR
dc.subjectCombinatória poliédricapt_BR
dc.subjectMáximo subgrafo comumpt_BR
dc.subjectProgramação linear inteirapt_BR
dc.subjectAlgoritmo Branch and Boundpt_BR
dc.subjectAlgoritmo Branch and Cutpt_BR
dc.titlePolyhedral study of the maximum common induced subgraph problempt_BR
dc.identifier.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.