Efficient Suboptimal Graph Isomorphism

DOI10.1007/978-3-642-02124-4_13MaRDI QIDQ3637695zbMATH OpenOpenAlexFDO

Authors Kaspar Riesen, Stefan Fankhauser, Peter J. C. Dickinson, Horst Bunke

Publication date 14 July 2009

Published in Graph-Based Representations in Pattern Recognition (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02124-4_13

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Speeding up graph edit distance computation through fast bipartite matching
• A graph isomorphism algorithm for object recognition
• Bipartite Graph Matching for Computing the Edit Distance of Graphs
• VF2++ -- an improved subgraph isomorphism algorithm
• Publication:5701586

Cites work

• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1222894 (Why is no real title available?)
• A Correspondence Measure for Graph Matching Using the Discrete Quantum Walk
• A graph distance measure for image analysis
• Algorithms for the Assignment and Transportation Problems
• An Algorithm for Subgraph Isomorphism
• An eigendecomposition approach to weighted graph matching problems
• Constraint satisfaction algorithms for graph pattern matching
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Matching graphs with unique node labels

Cited in

(15)

• Succinct Encodings of Graph Isomorphism
• An algorithm using length-r paths to approximate subgraph isomorphism
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• scientific article; zbMATH DE number 1941159 (Why is no real title available?)
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Graph-Based Representations in Pattern Recognition
• Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
• scientific article; zbMATH DE number 2033159 (Why is no real title available?)
• An Algorithm Portfolio for the Sub-graph Isomorphism Problem
• Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
• On the complexity of submap isomorphism and maximum common submap problems
• Speeding up graph edit distance computation through fast bipartite matching
• Benchmark Graphs for Practical Graph Isomorphism
• scientific article; zbMATH DE number 1759547 (Why is no real title available?)
• VF2++ -- an improved subgraph isomorphism algorithm

Describes a project that uses

Uses Software

• nauty

This page was built for publication: Efficient Suboptimal Graph Isomorphism

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