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

computational experimentspolyhedral combinatoricsgraph isomorphismcomputational resultsnumber of edgesbranch-and-cut algorithmsmaximum common subgraph problem

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1432332 (Why is no real title available?)
• 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
• Multiprocessor scheduling under precedence constraints: polyhedral results
• RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs

Cited in

(9)

• Graph comparison via nonlinear quantum search
• 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?)
• Spectral classes of regular, random, and empirical graphs
• Formulations for the maximum common edge subgraph problem
• A polyhedral study of the maximum edge subgraph problem
• A branch \& cut algorithm for the maximum common edge subgraph problem
• Polyhedral study of the maximum common induced subgraph problem
• A processor architecture design method for improving reusability of special-purpose superconducting quantum processor

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)