Advanced search
Start date
Betweenand


The maximum common edge subgraph problem: A polyhedral investigation

Full text
Author(s):
Bahiense, Laura ; Manic, Gordana ; Piva, Breno ; de Souza, Cid C.
Total Authors: 4
Document type: Journal article
Source: DISCRETE APPLIED MATHEMATICS; v. 160, n. 18, p. 19-pg., 2012-12-01.
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. (AU)

FAPESP's process: 08/06508-8 - Discrete optimization and graphs: algorithms, theory and applications
Grantee:Gordana Manic
Support Opportunities: Research Grants - Young Investigators Grants