A fast discovery algorithm for large common connected induced subgraphs
From MaRDI portal
Publication:2274094
DOI10.1016/j.dam.2019.02.023zbMath1419.05140OpenAlexW2931872765MaRDI QIDQ2274094
Luca Versari, Andrea Marino, Lorenzo Tattini, Roberto Grossi, Alessio Conte
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
Extremal problems in graph theory (05C35) Applications of graph theory (05C90) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Mathematical biology in general (92B99)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- An exact algorithm for the maximum clique problem
- Subgraph isomorphism, matching relational structures and maximal cliques
- Finding largest subtrees and smallest supertrees
- Enumerating all connected maximal common subgraphs in two graphs
- A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
- Finding maximal common subgraphs via time-space efficient reverse search
- Reverse search for enumeration
- Maximum common induced subgraph parameterized by vertex cover
- A note on the derivation of maximal common subgraphs of two directed or undirected graphs
- Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay
- Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Backtrack search algorithms and the maximal common subgraph problem
- An Algorithm for Subgraph Isomorphism
- RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs
- On the approximability of the maximum common subgraph problem
- Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs
- Graph-Based Representations in Pattern Recognition
- Algorithm 457: finding all cliques of an undirected graph
- Computing and Combinatorics
This page was built for publication: A fast discovery algorithm for large common connected induced subgraphs
