The maximum common edge subgraph problem: A polyhedral investigation

dc.creatorBahiense, L
dc.creatorManic, G
dc.creatorPiva, B
dc.creatorde Souza, CC
dc.date2012
dc.dateDEC
dc.date2014-07-30T19:38:37Z
dc.date2015-11-26T17:51:38Z
dc.date2014-07-30T19:38:37Z
dc.date2015-11-26T17:51:38Z
dc.date.accessioned2018-03-29T00:35:02Z
dc.date.available2018-03-29T00:35:02Z
dc.identifierDiscrete Applied Mathematics. Elsevier Science Bv, v. 160, n. 18, n. 2523, n. 2541, 2012.
dc.identifier0166-218X
dc.identifierWOS:000310667700004
dc.identifier10.1016/j.dam.2012.01.026
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/73614
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/73614
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1290026
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionIn the Maximum Common Edge Subgraph Problem (MCES), given two graphs G and H with the same number of vertices, one has to find a common subgraph of G and H (not necessarily induced) with the maximum number of edges. This problem arises in parallel programming environments, and was first defined in Bokhari (1981) [2]. This paper presents a new integer programming formulation for the MCES and a polyhedral study of this model. Several classes of valid inequalities are identified, most of which are shown to define facets. These findings were incorporated into a branch&cut algorithm we implemented. Experimental results with this algorithm are reported. (C) 2012 Elsevier B.V. All rights reserved.
dc.description160
dc.description18
dc.descriptionSI
dc.description2523
dc.description2541
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionCNPq [473726/2007-6, 555906/2010-8, 301732/2007-8, 472504/2007-0]
dc.descriptionFAPESP [2008/06508-8]
dc.languageen
dc.publisherElsevier Science Bv
dc.publisherAmsterdam
dc.publisherHolanda
dc.relationDiscrete Applied Mathematics
dc.relationDiscret Appl. Math.
dc.rightsfechado
dc.rightshttp://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy
dc.sourceWeb of Science
dc.subjectMaximum common subgraph problem
dc.subjectGraph isomorphism
dc.subjectPolyhedral combinatorics
dc.subjectBranch&cut algorithm
dc.subjectMapping Problem
dc.subjectAlgorithm
dc.subjectHeuristics
dc.subjectGraphs
dc.titleThe maximum common edge subgraph problem: A polyhedral investigation
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución