Enumerating all connected maximal common subgraphs in two graphs
We represent a new method for finding all connected maximal common subgraphs in two graphs which is based on the transformation of the problem into the clique problem. We have developed new algorithms for enumerating all cliques that represent connected maximal common subgraphs. These algorithms are based on variants of the Bron-Kerbosch algorithm. In this paper we explain the transformation of the maximal common subgraph problem into the clique problem. We give a short summary of the variants of the Bron-Kerbosch algorithm in order to explain the modification of that algorithm such that the detected cliques represent connected maximal common subgraphs. After introducing and proving several variants of the modified algorithm we discuss the runtimes for all variants by means of random graphs. The results show the drastical reduction of the runtimes for the new algorithms.
- Finding maximal common subgraphs via time-space efficient reverse search
- Computing and Combinatorics
- Graph-Based Representations in Pattern Recognition
- Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms
- scientific article; zbMATH DE number 2090205
- A branch and bound algorithm for the maximum clique problem
- A node covering algorithm
- A note on the derivation of maximal common subgraphs of two directed or undirected graphs
- A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
- Algorithm 457: finding all cliques of an undirected graph
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Clique detection for nondirected graphs: Two new algorithms
- Cliques of a graph-variations on the Bron-Kerbosch algorithm
- Finding a Maximum Clique in an Arbitrary Graph
- Finding a Maximum Independent Set
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 4081609 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3446920 (Why is no real title available?)
- On cliques in graphs
- The Enumeration of Maximal Cliques of Large Graphs
- Isolation concepts for clique enumeration: comparison and computational experiments
- Efficiently enumerating all maximal cliques with bit-parallelism
- On the complexity of submap isomorphism and maximum common submap problems
- The journey of graph kernels through two decades
- Finding maximal common subgraphs via time-space efficient reverse search
- A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
- A fast discovery algorithm for large common connected induced subgraphs
- Enumerating all maximal biclusters in numerical datasets
- Comparing and distinguishing the structure of biological branching
- All roads lead to Rome -- new search methods for the optimal triangulation problem
- Maximum common induced subgraph parameterized by vertex cover
- A linear time algorithm for maximal clique enumeration in large sparse graphs
- Maximal independent sets in clique-free graphs
- scientific article; zbMATH DE number 3890750 (Why is no real title available?)
- Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms
- Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
- \textsc{Rime}: repeat identification
- Sampling-based box-covering algorithm for renormalization of networks
- Graph-Based Representations in Pattern Recognition
- Enumerating Isolated Cliques in Synthetic and Financial Networks
- Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree
- A shift-based model to solve the integrated staff rostering and task assignment problem with real-world requirements
- Reasoning on property graphs with graph generating dependencies
- Faster maximal clique enumeration in large real-world link streams
- Convex covering using collections of convex polygons and set cover
- Listing maximal H-free subgraphs
- An algorithm for reporting maximal \(c\)-cliques
- Communicability graph and community structures in complex networks
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Computing maximal cliques in link streams
- Refined pivot selection for maximal clique enumeration in graphs
- A note on the problem of reporting maximal cliques
This page was built for publication: Enumerating all connected maximal common subgraphs in two graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1589412)
