TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

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

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut311-325
Sivumäärä15
JulkaisuAdvances in Computational Mathematics
Vuosikerta39
Numero2
DOI - pysyväislinkit
TilaJulkaistu - elokuuta 2013
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

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.

Tutkimusalat