Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)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.16018SI25232541Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)CNPq [473726/2007-6, 555906/2010-8, 301732/2007-8, 472504/2007-0]FAPESP [2008/06508-8]