Brasil
| Artículos de revistas
The maximum common edge subgraph problem: A polyhedral investigation
| dc.creator | Bahiense, L | |
| dc.creator | Manic, G | |
| dc.creator | Piva, B | |
| dc.creator | de Souza, CC | |
| dc.date | 2012 | |
| dc.date | DEC | |
| dc.date | 2014-07-30T19:38:37Z | |
| dc.date | 2015-11-26T17:51:38Z | |
| dc.date | 2014-07-30T19:38:37Z | |
| dc.date | 2015-11-26T17:51:38Z | |
| dc.date.accessioned | 2018-03-29T00:35:02Z | |
| dc.date.available | 2018-03-29T00:35:02Z | |
| dc.identifier | Discrete Applied Mathematics. Elsevier Science Bv, v. 160, n. 18, n. 2523, n. 2541, 2012. | |
| dc.identifier | 0166-218X | |
| dc.identifier | WOS:000310667700004 | |
| dc.identifier | 10.1016/j.dam.2012.01.026 | |
| dc.identifier | http://www.repositorio.unicamp.br/jspui/handle/REPOSIP/73614 | |
| dc.identifier | http://repositorio.unicamp.br/jspui/handle/REPOSIP/73614 | |
| dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/1290026 | |
| dc.description | Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) | |
| dc.description | Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) | |
| dc.description | 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. | |
| dc.description | 160 | |
| dc.description | 18 | |
| dc.description | SI | |
| dc.description | 2523 | |
| dc.description | 2541 | |
| dc.description | Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) | |
| dc.description | Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) | |
| dc.description | Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) | |
| dc.description | Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) | |
| dc.description | CNPq [473726/2007-6, 555906/2010-8, 301732/2007-8, 472504/2007-0] | |
| dc.description | FAPESP [2008/06508-8] | |
| dc.language | en | |
| dc.publisher | Elsevier Science Bv | |
| dc.publisher | Amsterdam | |
| dc.publisher | Holanda | |
| dc.relation | Discrete Applied Mathematics | |
| dc.relation | Discret Appl. Math. | |
| dc.rights | fechado | |
| dc.rights | http://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy | |
| dc.source | Web of Science | |
| dc.subject | Maximum common subgraph problem | |
| dc.subject | Graph isomorphism | |
| dc.subject | Polyhedral combinatorics | |
| dc.subject | Branch&cut algorithm | |
| dc.subject | Mapping Problem | |
| dc.subject | Algorithm | |
| dc.subject | Heuristics | |
| dc.subject | Graphs | |
| dc.title | The maximum common edge subgraph problem: A polyhedral investigation | |
| dc.type | Artículos de revistas |