Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: The maximum common edge subgraph problem: A polyhedral investigation
Author: Bahiense, L
Manic, G
Piva, B
de Souza, CC
Abstract: In 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.
Subject: Maximum common subgraph problem
Graph isomorphism
Polyhedral combinatorics
Branch&cut algorithm
Country: Holanda
Editor: Elsevier Science Bv
Citation: Discrete Applied Mathematics. Elsevier Science Bv, v. 160, n. 18, n. 2523, n. 2541, 2012.
Rights: fechado
Identifier DOI: 10.1016/j.dam.2012.01.026
Date Issue: 2012
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000310667700004.pdf389.25 kBAdobe PDFView/Open

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