Formulations for the maximum common edge subgraph problem

DOI10.1016/J.DAM.2023.11.044MaRDI QIDQ6193953zbMATH OpenOpenAlexFDO

Authors Etienne de Gastines, Arnaud Knippel

Publication date 14 February 2024

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

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

zbMATH Keywords

0-1 programminggraph matchingmaximum common subgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Integer programming (90C10)

Recommendations

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

Cites work

• A branch \& cut algorithm for the maximum common edge subgraph problem
• A large database of graphs and its use for benchmarking graph isomorphism algorithms
• scientific article; zbMATH DE number 1432332 (Why is no real title available?)
• The maximum common edge subgraph problem: A polyhedral investigation

Cited in

(1)

• PathLAD+: Towards effective exact methods for subgraph isomorphism problem

This page was built for publication: Formulations for the maximum common edge subgraph problem

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