Tampere University of Technology

TUTCRIS Research Portal

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

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Pages (from-to)311-325
Number of pages15
JournalAdvances in Computational Mathematics
Volume39
Issue number2
DOIs
Publication statusPublished - Aug 2013
Publication typeA1 Journal article-refereed

Abstract

The search for an easily computable, finite, complete set of graph invariants remains a challenging research topic. All measures characterizing the topology of a graph that have been developed thus far exhibit some degree of degeneracy, i.e., an inability to distinguish between non-isomorphic graphs. In this paper, we show that certain graph invariants can be useful in substantially reducing the computational complexity of isomorphism testing. Our findings are underpinned by numerical results based on a large scale statistical analysis.

Keywords

  • Graph isomorphism, Graph measures, Graph topology, Graphs, Uniqueness