Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms

DOI10.1007/978-3-540-87477-5_39zbMath1160.90681OpenAlexW1861597632MaRDI QIDQ3627718

B. Valery, Philippe Vismara

Publication date: 13 May 2009

Published in: Communications in Computer and Information Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-87477-5_39

zbMATH Keywords

subdivision graphcompatibility graphmaximum common subgraphlinegraphclique detectionconstraints satisfaction algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Measuring similarity between connected graphs: the role of induced subgraphs and complementarity eigenvalues, A fast discovery algorithm for large common connected induced subgraphs, Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree

Uses Software

• CPGraph
• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
• Enumerating all connected maximal common subgraphs in two graphs
• A note on the derivation of maximal common subgraphs of two directed or undirected graphs
• CP(Graph): Introducing a Graph Computation Domain in Constraint Programming
• Backtrack search algorithms and the maximal common subgraph problem
• Cliques of a graph-variations on the Bron-Kerbosch algorithm
• Constraint satisfaction algorithms for graph pattern matching
• Algorithm 457: finding all cliques of an undirected graph