The maximum common edge subgraph problem: A polyhedral investigation

DOI10.1016/J.DAM.2012.01.026MaRDI QIDQ1759826zbMATH OpenOpenAlexWikidataFDO

Authors Laura Bahiense, Gordana Manić, Breno Piva, Cid Carvalho de Souza

Publication date 22 November 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.01.026

zbMATH Keywords

branch-and-cut algorithmscomputational experimentscomputational resultsgraph isomorphismmaximum common subgraph problemnumber of edgespolyhedral combinatorics

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Boolean programming (90C09) Integer programming (90C10) Combinatorial optimization (90C27)

Review text

The number of vertices of the graphs used during the experiments was less than 40, the estimated power of the computer used was 243 MFlops. The results of these exepriments are compared with those obtained by a Ultra Sparc 1 workstation with an estimated power of 205 MFlops.

Recommendations

• A branch \& cut algorithm for the maximum common edge subgraph problem
• Polyhedral study of the maximum common induced subgraph problem
• Computing and Combinatorics
• On the approximability of the maximum common subgraph problem
• On the complexity of the maximum common subgraph problem for partial \(k\)-trees of bounded degree

Cites work

• A branch-and-cut algorithm for the maximum cardinality stable set problem
• Conflict graphs in solving integer programming problems
• Genetic algorithm based heuristics for the mapping problem
• scientific article; zbMATH DE number 1432332 (Why is no real title available?)
• Multiprocessor scheduling under precedence constraints: polyhedral results
• RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs

Cited in

(9)

• Polyhedral study of the maximum common induced subgraph problem
• Graph comparison via nonlinear quantum search
• A branch \& cut algorithm for the maximum common edge subgraph problem
• Automatic inference of graph transformation rules using the cyclic nature of chemical reactions
• scientific article; zbMATH DE number 7380509 (Why is no real title available?)
• A polyhedral study of the maximum edge subgraph problem
• Formulations for the maximum common edge subgraph problem
• A processor architecture design method for improving reusability of special-purpose superconducting quantum processor
• Spectral classes of regular, random, and empirical graphs

This page was built for publication: The maximum common edge subgraph problem: A polyhedral investigation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759826)