A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics

DOI10.1007/s10472-013-9335-0zbMath1357.68184OpenAlexW1963920197WikidataQ115926710 ScholiaQ115926710MaRDI QIDQ2248525

Jan Ramon, Leander Schietgat, Maurice Bruynooghe

Publication date: 26 June 2014

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://lirias.kuleuven.be/handle/123456789/389466

zbMATH Keywords

graph miningchemoinformaticslearning structure-activity relationshipsmetrics for structured data

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Learning and adaptive systems in artificial intelligence (68T05) Graph algorithms (graph-theoretic aspects) (05C85) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Related Items

On the complexity of submap isomorphism and maximum common submap problems ⋮ On maximum common subgraph problems in series-parallel graphs ⋮ Finding Largest Common Substructures of Molecules in Quadratic Time ⋮ A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs ⋮ A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree ⋮ Largest Weight Common Subtree Embeddings with Distance Penalties ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree

Uses Software

• AFGen
• gSpan

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Effective feature construction by maximum common subgraph sampling
• The subgraph isomorphism problem for outerplanar graphs
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Enumerating all connected maximal common subgraphs in two graphs
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Video indexing and similarity retrieval by largest common subgraph detection using decision trees
• Algorithms for the Assignment and Transportation Problems
• Logical and Relational Learning
• Kernels for Structured Data
• Backtrack search algorithms and the maximal common subgraph problem
• A graph distance metric based on the maximal common subgraph
• RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs
• Faster Subtree Isomorphism
• ORIGAMI: A Novel and Effective Approach for Mining Representative Orthogonal Graph Patterns
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs