Mathematical modeling and applications of optimization problems related to search ...
Mathematical models and algorithmic study for rectangle escape problems
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 |