A branch&cut algorithm for the maximum common edge subgraph problem |
| |
| Institution: | Universidade Federal do ABC, SP, Brazil;Universidade Federal do Rio de Janeiro, RJ, Brazil;Universidade Estadual de Campinas, SP, Brazil;Institute of Computing, University of Campinas, São Paulo, Brazil;Institute of Computing, University of Campinas - UNICAMP, Campinas, Brazil;School of Mathematics, Cardiff University, Cardiff, CF24 4AG, UK;Institute of Computing, University of Campinas, Brazil;Indian Institute of Science Education and Research, Pune, India;University of Niš, Faculty of Sciences and Mathematics, Department of Mathematics, P.O. Box 224, 18000 Niš, Serbia |
| |
| Abstract: | We investigate the Maximum Common Edge Subgraph Problem (MCES) defined as follows. Given two graphs G and H with the same number of vertices, find a common subgraph of G and H (not necessary induced) with the maximum number of edges. This problem arises in parallel programming environments, and was first defined by Bokhari in S. Bokhari, On the mapping problem, IEEE Trans. Comput., C-30(3), 1981]. We present a new integer programming formulation for the MCES problem and carry out a polyhedral investigation of this model. A number of valid inequalities are identified, most of which are facet-defining. We also report on computational experiments. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
