A fast discovery algorithm for large common connected induced subgraphs

DOI10.1016/J.DAM.2019.02.023MaRDI QIDQ2274094zbMATH OpenOpenAlexFDO

Authors Alessio Conte, Roberto Grossi, Andrea Marino, Lorenzo Tattini, Luca Versari

Publication date 19 September 2019

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

Full work available at URL https://hal.inria.fr/hal-02338435/file/Laccis_WEPA_special_DAM.pdf

zbMATH Keywords

enumerationisomorphismsmaximal common subgraphsoutput sensitivity

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Applications of graph theory (05C90) Mathematical biology in general (92B99)

Recommendations

• Graph-Based Representations in Pattern Recognition
• Finding maximal common subgraphs via time-space efficient reverse search
• Finding largest common substructures of molecules in quadratic time
• An improved maximum common induced subgraph solver
• Computing and Combinatorics

Cites work

• A note on the derivation of maximal common subgraphs of two directed or undirected graphs
• A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
• Algorithm 457: finding all cliques of an undirected graph
• An Algorithm for Subgraph Isomorphism
• An exact algorithm for the maximum clique problem
• Backtrack search algorithms and the maximal common subgraph problem
• Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs
• Computing and Combinatorics
• Enumerating all connected maximal common subgraphs in two graphs
• Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay
• Finding largest subtrees and smallest supertrees
• Finding maximal common subgraphs via time-space efficient reverse search
• Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Graph-Based Representations in Pattern Recognition
• scientific article; zbMATH DE number 49554 (Why is no real title available?)
• Maximum common induced subgraph parameterized by vertex cover
• On the approximability of the maximum common subgraph problem
• RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs
• Reverse search for enumeration
• Subgraph isomorphism, matching relational structures and maximal cliques
• Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques

Cited in

(1)

• Graph-Based Representations in Pattern Recognition

Describes a project that uses

Uses Software

• Algorithm 457
• ChemmineR

This page was built for publication: A fast discovery algorithm for large common connected induced subgraphs

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