The maximum common edge subgraph problem: A polyhedral investigation

被引：28
作者：
Bahiense, Laura [2 ]
Manic, Gordana [1 ]
Piva, Breno [3 ]
de Souza, Cid C. [3 ]
机构：
[1] Univ Fed ABC, CMCC, Sao Paulo, SP, Brazil
[2] Univ Fed Rio de Janeiro, COPPE Prod, BR-21941 Rio De Janeiro, RJ, Brazil
[3] Univ Estadual Campinas, Inst Comp, BR-13081970 Campinas, SP, Brazil
来源：
DISCRETE APPLIED MATHEMATICS | 2012年 / 160卷 / 18期
基金：
巴西圣保罗研究基金会;
关键词：
Maximum common subgraph problem; Graph isomorphism; Polyhedral combinatorics; Branch&cut algorithm; MAPPING PROBLEM; ALGORITHM; HEURISTICS; GRAPHS;
D O I：
10.1016/j.dam.2012.01.026
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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.
引用
收藏
页码：2523 / 2541
页数：19
相关论文
共 16 条
[1]   Conflict graphs in solving integer programming problems [J].
Atamtürk, A ;
Nemhauser, GL ;
Savelsbergh, MWP .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 121 (01) :40-55
[2]  
BOKHARI SH, 1981, IEEE T COMPUT, V30, P207, DOI 10.1109/TC.1981.1675756
[3]   GENETIC ALGORITHM-BASED HEURISTICS FOR THE MAPPING PROBLEM [J].
CHOCKALINGAM, T ;
ARUNKUMAR, S .
COMPUTERS & OPERATIONS RESEARCH, 1995, 22 (01) :55-64
[4]   Multiprocessor scheduling under precedence constraints: Polyhedral results [J].
Coll, PE ;
Ribeiro, CC ;
de Souza, CC .
DISCRETE APPLIED MATHEMATICS, 2006, 154 (05) :770-801
[5]   TASK ALLOCATION ONTO A HYPERCUBE BY RECURSIVE MINCUT BIPARTITIONING [J].
ERCAL, F ;
RAMANUJAM, J ;
SADAYAPPAN, P .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1990, 10 (01) :35-44
[6]  
Halldorson M.M., 1994, COMMUNICATION UNPUB
[7]  
LEE SY, 1987, IEEE T COMPUT, V36, P433, DOI 10.1109/TC.1987.1676925
[8]  
Marenco J., 2002, P CLAIO 2002 11 C LA
[9]  
Marenco J., 1999, THESIS U BUENOS AIRE
[10]  
Marenco J., 2006, P CLAIO 2006 13 C LA
12