Polyhedral study of the maximum common induced subgraph problem

DOI10.1007/S10479-011-1019-8MaRDI QIDQ1761750zbMATH OpenOpenAlexWikidataFDO

Authors Breno Piva, Cid Carvalho de Souza

Publication date 15 November 2012

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://ri.ufs.br/handle/riufs/1705

zbMATH Keywords

maximum cliqueinteger programmingpolyhedral combinatoricsbranch-and-cutbranch-and-boundmaximum common induced subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) 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
• On the approximability of the maximum common subgraph problem

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1335845 (Why is no real title available?)
• scientific article; zbMATH DE number 2043361 (Why is no real title available?)
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• A fast algorithm for the maximum clique problem
• Backtrack search algorithms and the maximal common subgraph problem
• Computing and Combinatorics
• RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs
• The structure-mapping engine: Algorithm and examples
• Video indexing and similarity retrieval by largest common subgraph detection using decision trees
• \(E_{11}\) and M theory

Cited in

(6)

• An improved maximum common induced subgraph solver
• Maximum common induced subgraph parameterized by vertex cover
• Polyhedral study of the connected subgraph problem
• Formulations for the maximum common edge subgraph problem
• A polyhedral study of the maximum edge subgraph problem
• The maximum common edge subgraph problem: A polyhedral investigation

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Polyhedral study of the maximum common induced subgraph problem

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