Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs

DOI10.7155/JGAA.00139MaRDI QIDQ5301407zbMATH OpenOpenAlexWikidataFDO

Authors Donatello Conte, Pasquale Foggia, Mario Vento

Publication date 19 January 2009

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://eudml.org/doc/55424, http://www.emis.de/journals/JGAA/accepted/2007/ConteFoggiaVento2007.11.1.pdf

zbMATH Keywords

graph matching algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Nonnumerical algorithms (68W05) Database theory (68P15)

Recommendations

• scientific article; zbMATH DE number 2043361
• scientific article; zbMATH DE number 2090205
• An algorithm for maximum common subgraph of planar triangulation graphs
• A large database of graphs and its use for benchmarking graph isomorphism algorithms
• scientific article; zbMATH DE number 2043360

Cited in

(14)

• scientific article; zbMATH DE number 2043361 (Why is no real title available?)
• scientific article; zbMATH DE number 2090205 (Why is no real title available?)
• Heuristics for the generalized median graph problem
• An algorithm for maximum common subgraph of planar triangulation graphs
• Answering ``why empty? and ``why so many? queries in graph databases
• A fast discovery algorithm for large common connected induced subgraphs
• Pattern Matching and Pattern Discovery Algorithms for Protein Topologies
• Graph-Based Representations in Pattern Recognition
• Recursive-Parallel Algorithm for Solving the Maximum Common Subgraph Problem
• Video indexing and similarity retrieval by largest common subgraph detection using decision trees
• Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms
• Isomorphism testing via polynomial-time graph extensions
• An appraisal of the performance of the MMSC subgraph generation algorithm on a Cyber system 170/720
• Median graphs: A genetic approach based on new theoretical properties

This page was built for publication: Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs

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