An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants

DOI10.1007/s10444-012-9281-0zbMath1270.05071OpenAlexW2004014250MaRDI QIDQ360469

Abbe Mowshowitz, Martin Grabner, Matthias Dehmer, Frank Emmert-Streib

Publication date: 27 August 2013

Published in: Advances in Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10444-012-9281-0

zbMATH Keywords

graph topologyuniquenessgraph isomorphismgraph measures

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

Sharp lower bounds on the Narumi-Katayama index of graph operations ⋮ Graph measures with high discrimination power revisited: a random polynomial approach ⋮ Towards detecting structural branching and cyclicity in graphs: a polynomial-based approach ⋮ On the degeneracy of the Randić entropy and related graph measures ⋮ On efficient network similarity measures ⋮ Highly unique network descriptors based on the roots of the permanental polynomial

Uses Software

• nauty
• R
• QuACN
• bliss

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A history of graph entropy measures
• Graph isomorphism problem
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• A graph isomorphism algorithm for object recognition
• A comparative analysis of the Tanimoto index and graph edit distance for measuring the topological similarity of trees
• On Graph Complexity
• Series expansion of the directed percolation probability
• An Algorithm for Subgraph Isomorphism
• The graph isomorphism disease
• Isomorph-Free Exhaustive Generation
• Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs
• Numerical Analysis of a Unilateral Problem in Planar Thermoelasticity
• Entropy and the complexity of graphs: I. An index of the relative complexity of a graph
• An Efficient Algorithm for Graph Isomorphism

This page was built for publication: An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants