An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants
Research output: Contribution to journal › Article › Scientific › peer-review
|Number of pages||15|
|Journal||Advances in Computational Mathematics|
|Publication status||Published - Aug 2013|
|Publication type||A1 Journal article-refereed|
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.