VF2++ -- an improved subgraph isomorphism algorithm

DOI10.1016/J.DAM.2018.02.018MaRDI QIDQ1744243zbMATH OpenOpenAlexWikidataFDO

Authors Alpár Jüttner, Péter Madarasi

Publication date 20 April 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2018.02.018

zbMATH Keywords

computational biologysubgraph isomorphism problem

Mathematics Subject Classification ID

Applications of graph theory (05C90) Protein sequences, DNA sequences (92D20) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Efficient Suboptimal Graph Isomorphism
• scientific article; zbMATH DE number 4081609
• A new algorithm for induced subgraph isomorphism
• An Algorithm Portfolio for the Sub-graph Isomorphism Problem
• Computing and Drawing Isomorphic Subgraphs

Cites work

• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• AllDifferent-based filtering for subgraph isomorphism
• An Algorithm for Subgraph Isomorphism
• Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism
• Colored hypergraph isomorphism is fixed parameter tractable
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On testing isomorphism of permutation graphs
• The complexity of theorem-proving procedures

Cited in

(8)

• Efficient Suboptimal Graph Isomorphism
• Indexing with well-founded total order for faster subgraph isomorphism detection
• VF2++
• Correct filtering for subgraph isomorphism search in compressed vertex-labeled graphs
• Localized RETE for incremental graph queries with nested graph conditions
• SLF: a passive parallelization of subgraph isomorphism
• PathLAD+: Towards effective exact methods for subgraph isomorphism problem
• GMFOLD: subgraph matching for high-throughput DNA-aptamer secondary structure classification and machine learning interpretability

Describes a project that uses

Uses Software

• LEMON

This page was built for publication: VF2++ -- an improved subgraph isomorphism algorithm

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